Гимади Э.Х.
Полиномиальные алгоритмы с оценками точности для некоторых задач поиска реберно-несмежных подграфов экстремального веса в полном взвешенном графе
Часто задачи дискретной оптимизации на полном взвешенном графе связаны с отысканием некоторого подграфа экстремального суммарного веса. К числу таких задач относятся задача коммивояжера, задача поиска клики заданного размера, задача отыскания остовного дерева и др. В последнее время актуальными стали задачи, в которых требуется найти два и более таких подграфов. Некоторые из этих проблем являются эффективно решаемыми (например, проблема нахождения нескольких реберно непересекающихся остовных деревьев минимальной суммарного веса). Однако чаще эти задачи являются NP-трудными. Настоящий доклад посвящен построению полиномиальных алгоритмов с оценками качества для отыскания нескольких реберно-непересекающихся подграфов в полном взвешенном графе применительно к задачам маршрутизации (задачи нескольких коммивояжеров), многослойной трехиндексной задаче о назначениях и к задаче поиска нескольких вершинно-несмежных клик заданного размера.
К списку докладов