Previous [1] [2] [3] [4] [5] [6] [7] [8] [9] [10]

¡@

Journal of Information Science and Engineering, Vol.19 No.5, pp.827-838 (September 2003)


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.

Keywords: graph algorithms, distance-hereditary graphs, cographs, Hamiltonian cycle, path cover

Full Text (¥þ¤åÀÉ) Retrieve PDF document (200309_06.pdf)

Received December 20, 2001; revised July 15, 2002; accepted August 27, 2002.
Communicated by Gen-Huey Chen.