Гамильтоново дополнение

Задача гамильтонова дополнения — это задача нахождения минимального числа рёбер, которое нужно добавить в граф, чтобы он стал гамильтоновым.

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

Более того, Ву, Лу и Ли показали, что существование эффективных алгоритмов с постоянным коэффициентом аппроксимации для этой задачи маловероятно[1].

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

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

Примечания

  1. Wu, Lu, Lee, 2000, с. 156 – 167.
  2. Takamizawa, Nishizeki, Saito, 1982, с. 623–641.
  3. Корниенко, 1984, с. 109-111.
  4. Raychaudhuri, 1995, с. 299 – 306.
  5. Agnetis, Detti, Meloni, Pacciarelli, 2001, с. 17 – 24.
  6. Detti, Meloni, 2004, с. 197 – 215.
  7. Gamarnik, Sviridenko, 2005, с. 139 – 158.

Литература

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.