Hamiltoni kiegészítés

A Hamilton-komplementációs probléma annak a problémája, hogy megtaláljuk az élek minimális számát, amelyet hozzá kell adni egy gráfhoz , hogy Hamilton -féle legyen .

Nyilvánvaló, hogy a probléma általában NP-nehéz (mert megoldása megválaszolja azt az NP-teljes problémát , amely annak meghatározására vonatkozik, hogy egy gráfnak van-e Hamilton-ciklusa ). Az ezzel kapcsolatos eldönthetőségi probléma , hogy egy adott gráfhoz K él hozzáadása képes-e Hamilton-gráfot létrehozni, NP-teljes.

Sőt, Wu, Lu és Li kimutatta, hogy nem valószínű, hogy erre a problémára hatékony algoritmusok léteznének állandó közelítési együtthatóval [1] .

A probléma polinomiális időben megoldható néhány gráfosztály esetében, amelyek magukban foglalják a párhuzamos soros gráfokat [2] és azok általánosításait [3] , amelyek külső síkbeli gráfokat tartalmaznak . Ezek az osztályok magukban foglalják a fasor gráfokat [4] [5] és a kaktuszok [6] .

Gamarnik és Sviridenko egy lineáris időfa-probléma segítségével tanulmányozta azon élek aszimptotikus számát, amelyeket a ritka véletlenszerű gráfokhoz hozzá kell adni ahhoz , hogy Hamiltoni gráfok legyenek [7] .

Jegyzetek

1. ↑ Wu, Lu, Lee, 2000 , p. 156-167.
2. ↑ Takamizawa, Nishizeki és Saito, 1982 , p. 623–641.
3. ↑ Kornienko, 1984 , p. 109-111.
4. ↑ Raychaudhuri, 1995 , p. 299-306.
5. ↑ Agnetis, Detti, Meloni, Pacciarelli, 2001 , p. 17-24.
6. ↑ Detti, Meloni, 2004 , p. 197-215.
7. ↑ Gamarnik, Sviridenko, 2005 , p. 139-158.

Irodalom

• Takamizawa K., Nishizeki T., Saito N. Kombinatorikus problémák lineáris idejű kiszámíthatósága sorozat-párhuzamos gráfokon // Journal of the ACM . - 1982. - T. 29 , sz. 3 . – S. 623–641 . - doi : 10.1145/322326.322328 .
• Wu QS, Lu CL, Lee RCT An Approximate Algorithm for the Weighted Hamilton Path Completion Problem on a Tree // Algorithms and Computation / Goos G., Hartmanis J., van Leeuwen J.. 11th International Conference, ISAAC 2000. Taipei, Tajvan , 2000. december 18-20. Proceedings. - Springer, 2000. - T. 1969. - (Számítástechnikai előadásjegyzetek). — ISBN 3-540-41255-7 .  (nem elérhető link)
• Korneyenko NM Kombinatorikus algoritmusok gráfok osztályán // Discrete Applied Mathematics . - 1994. - T. 54 , sz. 2-3 .
• Raychaudhuri A. Egy fa teljes intervallumszáma és vonalgráfjának Hamilton befejezési száma . — Információfeldolgozási levelek. - 1995. - T. 56.
• Agnetis A., Detti P., Meloni C., Pacciarelli D. Lineáris algoritmus egy fa vonalgráfjának Hamiltoni befejezési számához . — Információfeldolgozási levelek. - 2001. - T. 79.
• Detti P., Meloni C. Lineáris algoritmus egy kaktusz vonalgráfjának Hamiltoni befejezési számához  // Discrete Applied Mathematics. - 2004. - február ( 136. évf. , 2-3. szám ).
  • N.M. Kornyienko. Kombinatorikus algoritmusok a gráfok osztályán // Proceedings of the National Academy of Sciences of Belarus FIZIKAI ÉS TECHNIKAI TUDOMÁNYOK SOROZATA. - 1984. - Kiadás. 3 . - S. 109-111 .
• Gamarnik D., Sviridenko M. Ritka véletlen gráfok hamiltoni befejezései  // Discrete Applied Mathematics. - 2005. - T. 152 .