𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Exact algorithms for the Hamiltonian cycle problem in planar graphs

✍ Scribed by Vladimir G. Deı˘neko; Bettina Klinz; Gerhard J. Woeginger

Publisher
Elsevier Science
Year
2006
Tongue
English
Weight
167 KB
Volume
34
Category
Article
ISSN
0167-6377

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

On the number of hamiltonian cycles in a
On the number of hamiltonian cycles in a maximal planar graph
✍ S. L. Hakimi; E. F. Schmeichel; C. Thomassen 📂 Article 📅 1979 🏛 John Wiley and Sons 🌐 English ⚖ 243 KB 👁 2 views

## Abstract We consider the problem of the minimum number of Hamiltonian cycles that could be present in a Hamiltonian maximal planar graph on __p__ vertices. In particular, we construct a __p__‐vertex maximal planar graph containing exactly four Hamiltonian cycles for every __p__ ≥ 12. We also pro

Linear-time certifying algorithms for th
Linear-time certifying algorithms for the path cover and Hamiltonian cycle problems on interval graphs
✍ Ruo-Wei Hung; Maw-Shang Chang 📂 Article 📅 2011 🏛 Elsevier Science 🌐 English ⚖ 252 KB

A certifying algorithm for a problem is an algorithm that provides a certificate with each answer that it produces. The certificate is an evidence that can be used to authenticate the correctness of the answer. A Hamiltonian cycle in a graph is a simple cycle in which each vertex of the graph appear