Exact algorithms for the Hamiltonian cycle problem in planar graphs

V.G. Deineko, B. Klinz, G.J. Woeginger

Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer review

18 Citaten (Scopus)
1 Downloads (Pure)

Samenvatting

We construct an exact algorithm for the Hamiltonian cycle problem in planar graphs with worst case time complexity , where c is some fixed constant that does not depend on the instance. Furthermore, we show that under the exponential time hypothesis, the time complexity cannot be improved to .
Originele taal-2Engels
Pagina's (van-tot)269-274
TijdschriftOperations Research Letters
Volume34
Nummer van het tijdschrift3
DOI's
StatusGepubliceerd - 2006

Vingerafdruk Duik in de onderzoeksthema's van 'Exact algorithms for the Hamiltonian cycle problem in planar graphs'. Samen vormen ze een unieke vingerafdruk.

Citeer dit