Эта публикация цитируется в
3 статьях
Асимптотически точный подход к приближенному решению некоторых задач покрытия графа несмежными циклами
Э. Х. Гимади,
И. А. Рыков Институт математики им. С.Л. Соболева Сибирского отделения Российской академии наук, г. Новосибирск
Аннотация:
Рассматривается задача
$m$-CYCLES COVER о покрытии полного неориентированного графа
$m$ вершинно-несмежными циклами экстремального суммарного веса ребер. Представлен общий так называемый TSP-подход к построению приближенного алгоритма решения задачи с использованием решения задачи коммивояжера (TSP). Проведен анализ модификаций алгоритма для задачи Euclidean MAX
$m$-CYCLES COVER на детерминированных входах (весах ребер) в многомерном евклидовом пространстве и для задачи Random MIN
$m$-CYCLES COVER на случайных входах UNI
$(0,1)$. Показано, что оба алгоритма имеют временную сложность
$O(n^3)$ и являются асимптотически точными при числе покрывающих циклов
$m=o(n)$ и
$ m\le n^{1/3}/\ln n$ соответственно.
Ключевые слова:
покрытие графа циклами, задача коммивояжера, приближенные алгоритмы, вычислительная сложность, точность аппроксимации, асимптотическая оптимальность, случайные входы, вероятностный анализ.
УДК:
519.16 +
519.85 Поступила в редакцию: 10.05.2015