Проблема гамильтонова пополнения состоит в том, чтобы найти минимальное количество ребер, которое нужно добавить к графу, чтобы сделать его гамильтоновым .
Очевидно, что проблема NP-трудна в общем случае (поскольку ее решение дает ответ на NP-полную проблему определения того, имеет ли данный граф гамильтонов цикл ). Связанная с этим проблема принятия решения о том, можно ли добавить K ребер к данному графу для создания гамильтонова графа, является NP-полной.
Более того, гамильтоново пополнение относится к классу сложности APX , т. Е. Маловероятно, что для этой задачи существуют эффективные алгоритмы аппроксимации постоянного отношения . [1]
Задача может быть решена за полиномиальное время для некоторых классов графов, включая последовательно-параллельные графы [2] и их обобщения [3], которые включают внешнепланарные графы , а также для линейного графа дерева [4] [5] или кактусовый граф . [6]
Гамарник и др. используйте алгоритм линейного времени для решения задачи на деревьях, чтобы изучить асимптотическое количество ребер, которые необходимо добавить к разреженным случайным графам, чтобы сделать их гамильтоновыми. [7]
Ссылки [ править ]
- ^ QS Wu, CL Lu, RCT Lee, Приближенный алгоритм для взвешенной гамильтоновой задачи о завершении пути на дереве , Lecture Notes in Computer Science , Vol. 1969 (2000) Страницы: 156 - 167
- ^ Takamizawa, K .; Нишизеки, Т .; Сайто, N. (1982), "Линейное время Вычислимость комбинаторных задач на последовательно-параллельных графах", Журнал ACM , 29 (3): 623-641, DOI : 10,1145 / 322326,322328.
- ^ Н. М. Корнеенко, Комбинаторные алгоритмы на одном классе графов, Дискретная прикладная математика , т. 54, № 2–3, стр. 215–217, 1994.
- ^ Арундати Райчаудхури, Общее количество интервалов дерева и гамильтоново число завершения его линейного графа , Письма об обработке информации, том 56, выпуск 6 (декабрь 1995) 299-306
- ^ А. Агнетис, П. Детти, К. Мелони, Д. Паччарелли, Линейный алгоритм для гамильтонова числа завершения линейного графа дерева , Письма об обработке информации, том 79, выпуск 1 (май 2001), 17-24
- ^ Паоло Детти, Карло Мелони, Линейный алгоритм для гамильтонова числа завершения линейного графа кактуса , Дискретная прикладная математика, том 136, выпуск 2-3 (февраль 2004) 197 - 215
- ^ Дэвид Гамарник, Максим Свириденко, Гамильтоновы пополнения разреженных случайных графов , Дискретная прикладная математика 152 (2005) 139 - 158
