Гамильтоново пополнение - Hamiltonian completion

В Гамильтоново пополнение проблема состоит в том, чтобы найти минимальное количество ребер, которое нужно добавить к график сделать это Гамильтониан.

Проблема явно NP-жесткий в общем случае (так как его решение дает ответ на НП-полный проблема определения того, имеет ли данный граф Гамильтонов цикл ). Связанный проблема решения определения того, есть ли K ребра могут быть добавлены к данному графу, чтобы сделать гамильтонов граф NP-полным.

Более того, гамильтоново пополнение принадлежит APX класс сложности, т.е. вряд ли эффективная приближение постоянного отношения существуют алгоритмы для решения этой проблемы.[1]

Проблема может быть решена в полиномиальное время для определенных классов графов, в том числе последовательно-параллельные графы[2] и их обобщения,[3] который включает в себя внешнепланарные графы, а также для линейный график дерева[4][5]или кактус граф.[6]

Гамарник и др. используйте алгоритм линейного времени для решения задачи на деревьях, чтобы изучить асимптотическое количество ребер, которые должны быть добавлены для разреженных случайные графы сделать их гамильтоновыми.[7]

Рекомендации

  1. ^ К. С. Ву, К. Л. Лу, Р. К. Т. Ли, Приближенный алгоритм решения взвешенной гамильтоновой задачи о завершении пути на дереве, Конспект лекций по информатике, Vol. 1969 (2000) Страницы: 156 - 167
  2. ^ Takamizawa, K .; Нишизеки, Т.; Сайто Н. (1982), "Линейная вычислимость комбинаторных задач на последовательно-параллельных графах", Журнал ACM, 29 (3): 623–641, Дои:10.1145/322326.322328.
  3. ^ Корнеенко Н. М. Комбинаторные алгоритмы на одном классе графов. Дискретная прикладная математика, т.54, №2-3, с.215-217, 1994
  4. ^ Арундати Райчаудхури, Общее число интервалов дерева и число гамильтониана завершения его линейного графа, Письма по обработке информации, том 56, выпуск 6 (декабрь 1995) 299 - 306
  5. ^ А. Агнетис, П. Детти, К. Мелони, Д. Пачарелли, Линейный алгоритм для гамильтонова числа пополнения линейного графа дерева, Письма об обработке информации, том 79, выпуск 1 (май 2001 г.), 17–24
  6. ^ Паоло Детти, Карло Мелони, Линейный алгоритм для гамильтонова числа завершения линейного графика кактуса, Дискретная прикладная математика, том 136, выпуск 2-3 (февраль 2004 г.) 197 - 215
  7. ^ Давид Гамарник, Максим Свириденко, Гамильтоновы пополнения разреженных случайных графов, Дискретная прикладная математика 152 (2005) 139 - 158