Задача о декомпозиции множества путей ориентированного графа и ее приложение

Исследуется задача о декомпозиции множества путей ориентированного графа и ее приложение для снижения размерности прикладной задачи о назначении и перемещении локомотивов. На заданном множестве путей и наборе сильно связных подграфов определяется специальная таблица. Для решения графовой задачи о декомпозиции разработан эвристический алгоритм, основанный на идее быстрой сортировки построенной таблицы. Приводится оценка сложности алгоритма. Полученные результаты использованы для снижения размерности указанной прикладной задачи. Приводятся результаты вычислительных экспериментов.