Exact algorithms for the Hamiltonian cycle problem in planar graphs

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

doi:10.1016/j.orl.2005.04.013

Exact algorithms for the Hamiltonian cycle problem in planar graphs

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

Combinatorial Optimization

Research output: Contribution to journal › Article › Academic › peer-review

25 Citations (Scopus)

4 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 language	English
Pages (from-to)	269-274
Journal	Operations Research Letters
Volume	34
Issue number	3
DOIs	https://doi.org/10.1016/j.orl.2005.04.013
Publication status	Published - 2006

Access to Document

10.1016/j.orl.2005.04.013

Cite this

@article{9425995af1344a10a99760015331811e,

title = "Exact algorithms for the Hamiltonian cycle problem in planar graphs",

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 .",

author = "V.G. Deineko and B. Klinz and G.J. Woeginger",

year = "2006",

doi = "10.1016/j.orl.2005.04.013",

language = "English",

volume = "34",

pages = "269--274",

journal = "Operations Research Letters",

issn = "0167-6377",

publisher = "Elsevier B.V.",

number = "3",

}

TY - JOUR

T1 - Exact algorithms for the Hamiltonian cycle problem in planar graphs

AU - Deineko, V.G.

AU - Klinz, B.

AU - Woeginger, G.J.

PY - 2006

Y1 - 2006

N2 - 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 .

AB - 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 .

U2 - 10.1016/j.orl.2005.04.013

DO - 10.1016/j.orl.2005.04.013

M3 - Article

SN - 0167-6377

VL - 34

SP - 269

EP - 274

JO - Operations Research Letters

JF - Operations Research Letters

IS - 3

ER -

Exact algorithms for the Hamiltonian cycle problem in planar graphs

Abstract

Access to Document

Fingerprint

Cite this