| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 1143371 | Operations Research Letters | 2006 | 6 Pages |
Abstract
We construct an exact algorithm for the Hamiltonian cycle problem in planar graphs with worst case time complexity O(cn), 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 O(co(n)).
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Vladimir G. Deı˘neko, Bettina Klinz, Gerhard J. Woeginger,