Обзор алгоритмов поиска кратчайших путей в задачах сжатия топологии ИС

Представлен обзор известных решений теоретико-графовых задач, связанных с проблемой сжатия топологии ИС на графе ограничений. Рассмотрены алгоритмы поиска кратчайших путей и циклов отрицательной длины во взвешенном направленном графе. Приведены наиболее значимые работы, опубликованные за последние полстолетия, в которых центральным является вопрос алгоритмической сложности. Выяснены свойства графа ограничений, позволяющие повысить эффективность методов. Даны рекомендации по использованию тех или иных алгоритмов.
Малинаускас Костас Костович
Национальный исследовательский университет «МИЭТ», г. Москва, Россия
Поделиться