Exact algorithms for the Hamiltonian cycle problem in planar graphs

Exact algorithms for the Hamiltonian cycle problem in planar graphs

0.00 Avg rating0 Votes
Article ID: iaor20062883
Country: Netherlands
Volume: 34
Issue: 3
Start Page Number: 269
End Page Number: 274
Publication Date: May 2006
Journal: Operations Research Letters
Authors: , ,
Keywords: combinatorial analysis
Abstract:

We construct an exact algorithm for the Hamiltonian cycle problem in planar graphs with worst case time complexity O(c√(n)), 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))).

Reviews

Required fields are marked *. Your email address will not be published.