Exact algorithms for the Hamiltonian cycle problem in planar graphs

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

Research output: Contribution to journalArticleAcademicpeer-review

18 Citations (Scopus)
1 Downloads (Pure)

Abstract

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 .
Original languageEnglish
Pages (from-to)269-274
JournalOperations Research Letters
Volume34
Issue number3
DOIs
Publication statusPublished - 2006

Fingerprint Dive into the research topics of 'Exact algorithms for the Hamiltonian cycle problem in planar graphs'. Together they form a unique fingerprint.

Cite this