Recognition of perfect circular-arc graphs

被引：1

作者：

Cameron, Kathie ^{[1
]}

Eschen, Elaine A. ^{[2
]}

Hoang, Chinh T. ^{[3
]}

Sritharan, R. ^{[4
]}

机构：

[1] Wilfrid Laurier Univ, Dept Math, Waterloo, ON N2L 3C5, Canada

[2] West Virginia Univ, Lane Dept Comp Sci & Elect Engn, Morgantown, WV 26506 USA

[3] Wilfrid Laurier Univ, Dept Phys & Comp Sci, Waterloo, ON N2L 3C5, Canada

[4] Univ Dayton, Dept Comp Sci, Dayton, OH 45469 USA

来源：

GRAPH THEORY IN PARIS: PROCEEDINGS OF A CONFERENCE IN MEMORY OF CALUDE BERGE | 2007年

基金：

加拿大自然科学与工程研究理事会;

关键词：

circular-arc graph; perfect graph;

D O I：

10.1007/978-3-7643-7400-6_9

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

We give an o(mn log log n+ m(2))-time algorithm to recognize perfect circular-arc graphs.

引用

页码：97 / +

页数：3

共 20 条

[1] ARIKATI SR, 1991, BIT, V31, P182, DOI 10.1007/BF01931279
[2] A LINEAR ALGORITHM FOR THE GROUP PATH PROBLEM ON CHORDAL GRAPHS
ARIKATI, SR
PELED, UN
[J]. DISCRETE APPLIED MATHEMATICS, 1993, 44 (1-3) : 185 - 190
[3] Berge C, 2001, WIL INT S D, P1
[4] BIENSTOCK D, 1992, DISCRETE MATH, V102, P109
[5] BOAS PV, 1977, INFORMATION PROCESSI, V6, P80
[6] CAMERON K, 1990, DIMACS SERIES DISCRE, V1, P83
[7] Recognizing Berge graphs
Chudnovsky, M
Cornuéjols, G
Liu, XM
Seymour, P
Vuskovic, K
[J]. COMBINATORICA, 2005, 25 (02) : 143 - 186
[8] CHUDNOVSKY M, IN PRESS ANN MATH
[9] ESCHEN EM, 1993, PROCEEDINGS OF THE FOURTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, P128
[10] Everett H, 2001, WIL INT S D, P67