Linear-time algorithms for the Hamiltonian problems on distance-hereditary graphs

被引：22

作者：

Hung, RW ^{[1
]}

Chang, MS ^{[1
]}

机构：

[1] Natl Chung Cheng Univ, Dept Comp Sci & Informat Engn, Chiayi 621, Taiwan

来源：

THEORETICAL COMPUTER SCIENCE | 2005年 / 341卷 / 1-3期

关键词：

graph algorithms; linear-time algorithms; Hamiltonian problems; distance-hereditary graphs;

D O I：

10.1016/j.tcs.2005.04.009

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

A Hamiltonian path of a graph G is a simple path that contains each vertex of G exactly once. A Hamiltonian cycle of a graph is a simple cycle with the same property. The Hamiltonian path (resp. cycle) problem involves testing whether a Hamiltonian path (resp. cycle) exists in a graph. The 1HP (resp. 2HP) problem is to determine whether a graph has a Hamiltonian path starting from a specified vertex (resp. starting from a specified vertex and ending at the other specified vertex). The Hamiltonian problems include the Hamiltonian path, Hamiltonian cycle, 1HP, and 2HP problems. A graph is a distance-hereditary graph if each pair of vertices is equidistant in every connected induced subgraph containing them. In this paper, we present a unified approach to solving the Hamiltonian problems on distance-hereditary graphs in linear time. (c) 2005 Elsevier B.V. All rights reserved.

引用

页码：411 / 440

页数：30