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

Задача гамільтонового доповнення — це задача знаходження найменшого числа ребер, які потрібно додати в граф, щоб він став гамільтоновим.

Ясно, що задача в загальному випадку 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.

Література
  • Takamizawa K., Nishizeki T., Saito N. Linear-time computability of combinatorial problems on series-parallel graphs // Journal of the ACM. — 1982. — Т. 29, вип. 3 (3 листопада). — С. 623–641. — DOI:10.1145/322326.322328.
  • Wu Q. S., Lu C. L., Lee R. C. T. An Approximate Algorithm for the Weighted Hamiltonian Path Completion Problem on a Tree // Algorithms and Computation / Goos G., Hartmanis J., van Leeuwen J. — Springer, 2000. — Т. 1969. — (Lecture Notes in Computer Science) — ISBN 3-540-41255-7.[недоступне посилання з Март 2020]
  • Korneyenko N. M. Combinatorial algorithms on a class of graphs // Discrete Applied Mathematics. — 1994. — Т. 54, вип. 2-3 (3 листопада).
  • Raychaudhuri A. The total interval number of a tree and the Hamiltonian completion number of its line graph. — Information Processing Letters. — 1995. — Т. 56.
  • Agnetis A., Detti P., Meloni C., Pacciarelli D. A linear algorithm for the Hamiltonian completion number of the line graph of a tree. — Information Processing Letters. — 2001. — Т. 79.
  • Detti P., Meloni C. A linear algorithm for the Hamiltonian completion number of the line graph of a cactus // Discrete Applied Mathematics. — 2004. — Т. 136, вип. 2-3 (February).
    • Н.М. Корниенко. Комбинаторные алгоритмы на классе графов // Известия Национальной академии наук Беларуси СЕРИЯ ФИЗИКО-ТЕХНИЧЕСКИХ НАУК. — 1984. — Вип. 3 (3 листопада). — С. 109-111.
  • Gamarnik D., Sviridenko M. Hamiltonian completions of sparse random graphs // Discrete Applied Mathematics. — 2005. — Т. 152 (3 листопада).
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.