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

被引：30

作者：

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 [J].

BONUCCELLI, MA ;

BOVET, DP .

INFORMATION PROCESSING LETTERS, 1979, 8 (04) :159-161

[2]

Golumbic M., 1980, ALGORITHMIC GRAPH TH

[3] FINDING HAMILTONIAN CIRCUITS IN INTERVAL-GRAPHS [J].

KEIL, JM .

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 [J].

MANACHER, GK ;

MANKUS, TA ;

SMITH, CJ .

INFORMATION PROCESSING LETTERS, 1990, 35 (04) :205-211

← 1 →