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

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

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

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

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

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

Примечания

↑ Wu, Lu, Lee, 2000, с. 156 – 167.
↑ Takamizawa, Nishizeki, Saito, 1982, с. 623–641.
↑ Корниенко, 1984, с. 109-111.
↑ Raychaudhuri, 1995, с. 299 – 306.
↑ Agnetis, Detti, Meloni, Pacciarelli, 2001, с. 17 – 24.
↑ Detti, Meloni, 2004, с. 197 – 215.
↑ 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. — С. 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.. 11th International Conference, ISAAC 2000. Taipei, Taiwan, December 18-20, 2000 Proceedings. — Springer, 2000. — Т. 1969. — (Lecture Notes in Computer Science). — ISBN 3-540-41255-7. (недоступная ссылка)
Korneyenko N. M. Combinatorial algorithms on a class of graphs // Discrete Applied Mathematics. — 1994. — Т. 54, вып. 2-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).
- Н.М. Корниенко. Комбинаторные алгоритмы на классе графов // Известия Национальной академии наук Беларуси СЕРИЯ ФИЗИКО-ТЕХНИЧЕСКИХ НАУК. — 1984. — Вып. 3. — С. 109-111.
Gamarnik D., Sviridenko M. Hamiltonian completions of sparse random graphs // Discrete Applied Mathematics. — 2005. — Т. 152.

[_b8fdb1eff2025ccb-1] Wu, Lu, Lee, 2000, с. 156 – 167.

[_cc1d735d032b338a-2] Takamizawa, Nishizeki, Saito, 1982, с. 623–641.

[_13561582022e07f7-3] Корниенко, 1984, с. 109-111.

[_82e74179f0a77350-4] Raychaudhuri, 1995, с. 299 – 306.

[_17f240d3263c87fb-5] Agnetis, Detti, Meloni, Pacciarelli, 2001, с. 17 – 24.

[_d4c076e4bdd61077-6] Detti, Meloni, 2004, с. 197 – 215.

[_9062c7bb8c0446b4-7] Gamarnik, Sviridenko, 2005, с. 139 – 158.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

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

Примечания

Литература

Portal di Ensiklopedia Dunia