AN O(N2 LOG N) ALGORITHM FOR THE HAMILTONIAN CYCLE PROBLEM ON CIRCULAR-ARC GRAPHS

被引：29

作者：

SHIH, WK ^{[1
]}

CHERN, TC ^{[1
]}

HSU, WL ^{[1
]}

机构：

[1] NORTHWESTERN UNIV,DEPT IND ENGN & MANAGEMENT SCI,EVANSTON,IL 60208

来源：

SIAM JOURNAL ON COMPUTING | 1992年 / 21卷 / 06期

关键词：

GRAPH; PATH; ALGORITHM; HAMILTONIAN CYCLE;

D O I：

10.1137/0221061

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

A circular arc family F is a collection of arcs on a circle. A circular-arc graph is the intersection graph of an arc family. A Hamiltonian cycle (HC) in a graph is a cycle that passes through every vertex exactly once. This paper presents an O(n2 log n) algorithm to determine whether a given circular-arc graph contains an HC. This algorithm is based on two subroutines for interval graphs: (i) a linear time greedy algorithm for the node disjoint path cover problem and (ii) a linear time HC algorithm. If the given graph does not contain an HC, this paper can produce a proof either through the deletion of an appropriate cutset or through the failure to obtain a specific type of HC.

引用

页码：1026 / 1046

页数：21

共 4 条

[1] MINIMUM NODE DISJOINT PATH COVERING FOR CIRCULAR-ARC GRAPHS
BONUCCELLI, MA
BOVET, DP
[J]. INFORMATION PROCESSING LETTERS, 1979, 8 (04) : 159 - 161
[2] Golumbic M., 1980, ALGORITHMIC GRAPH TH
[3] FINDING HAMILTONIAN CIRCUITS IN INTERVAL-GRAPHS
KEIL, JM
[J]. INFORMATION PROCESSING LETTERS, 1985, 20 (04) : 201 - 206
[4] AN OPTIMUM O(N LOG N) ALGORITHM FOR FINDING A CANONICAL HAMILTONIAN PATH AND A CANONICAL HAMILTONIAN CIRCUIT IN A SET OF INTERVALS
MANACHER, GK
MANKUS, TA
SMITH, CJ
[J]. INFORMATION PROCESSING LETTERS, 1990, 35 (04) : 205 - 211

← 1 →