Hamiltonovské dokončení - Hamiltonian completion

The Hamiltonovské dokončení problém je najít minimální počet hran, které se mají přidat do a graf udělat to Hamiltonian.

Problém je jasně NP-tvrdé v obecném případě (protože jeho řešení dává odpověď na NP-kompletní problém určení, zda daný graf má a Hamiltonovský cyklus ). Přidružené rozhodovací problém rozhodování, zda K. hrany mohou být přidány k danému grafu, aby se vytvořil Hamiltonovský graf, který je NP-úplný.

Hamiltoniánské dokončení navíc patří k APX třída složitosti, tj. je nepravděpodobné, že efektivní aproximace konstantního poměru pro tento problém existují algoritmy.[1]

Problém lze vyřešit v polynomiální čas pro určité třídy grafů, včetně sériově paralelní grafy[2] a jejich zobecnění,[3] který zahrnuje vnější rovinné grafy, stejně jako pro hranový graf stromu[4][5]nebo a kaktusový graf.[6]

Gamarnik a kol. použijte lineární časový algoritmus pro řešení problému na stromech ke studiu asymptotického počtu hran, které je třeba přidat pro řídké náhodné grafy aby z nich byli Hamiltonovci.[7]

Reference

  1. ^ Q. S. Wu, C. L. Lu, R. C. T. Lee, Přibližný algoritmus pro vážený problém s dokončením Hamiltonovské cesty na stromě, Přednášky z informatiky, Sv. 1969 (2000), strany: 156-167
  2. ^ Takamizawa, K .; Nishizeki, T.; Saito, N. (1982), "Lineární časová vypočítatelnost kombinatorických problémů na sériově paralelních grafech", Deník ACM, 29 (3): 623–641, doi:10.1145/322326.322328.
  3. ^ N. M. Korneyenko, kombinatorické algoritmy na třídě grafů, Diskrétní aplikovaná matematika, v.54 ​​n.2-3, str.215-217, 1994
  4. ^ Arundhati Raychaudhuri, Celkový počet intervalů stromu a hamiltonovské číslo dokončení jeho spojnicového grafu, Information Processing Letters, svazek 56, číslo 6 (prosinec 1995) 299 - 306
  5. ^ A. Agnetis, P. Detti, C. Meloni, D. Pacciarelli, Lineární algoritmus pro hamiltonovské číslo dokončení řádkového grafu stromu „Information Processing Letters, svazek 79, číslo 1 (květen 2001), 17. - 24. den
  6. ^ Paolo Detti, Carlo Meloni, Lineární algoritmus pro hamiltonovské dokončovací číslo spojnicového grafu kaktusu, Discrete Applied Mathematics, svazek 136, vydání 2-3 (únor 2004) 197-215
  7. ^ David Gamarnik, Maxim Sviridenko, Hamiltonovské dokončení řídkých náhodných grafů, Discrete Applied Mathematics 152 (2005) 139 - 158