An algorithm for finding Hamiltonian Cycles in Cubic Planar Graphs

MaRDI QIDQ6268038zbMATH OpenFDO

Authors Bohao Yao, C. J. Ras, Hamid Mokhtar

Publication date 4 December 2015

Abstract: We first prove a one-to-one correspondence between finding Hamiltonian cycles in a cubic planar graphs and finding trees with specific properties in dual graphs. Using this information, we construct an exact algorithm for finding Hamiltonian cycles in cubic planar graphs. The worst case time complexity of our algorithm is O$(2^n)$.

This page was built for publication: An algorithm for finding Hamiltonian Cycles in Cubic Planar Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6268038)