Hamiltonian Cycle Problem on Distance-Hereditary Graphs
Ruo-Wei Hung, Shaur-Ching Wu and Maw-Shang Chang Department of Computer Science and Information Engineering National Chung Cheng University Chiayi, 621 Taiwan E-mail: {rwhung, mschang}@cs.ccu.edu.tw
A connected graph G = (V, E) is called distance-hereditary if every two vertices in V have the same distance in every connected induced subgraph of G containing them. This paper presents an O(|V|2) time algorithm for solving the Hamiltonian cycle problem on distance-hereditary graphs.