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

¡@

Hamiltonian Cycle Problem on Distance-Hereditary Graphs

**Ruo-Wei Hung, Shaur-Ching Wu and Maw-Shang Chang**

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

Retrieve PDF document (**200309_06.pdf**)

Received December 20, 2001; revised July 15, 2002; accepted August 27, 2002.

Communicated by Gen-Huey Chen.