Polynomial time recognition of unit circular-arc graphs

被引：11

作者：

Durán, G

Gravano, A

McConnell, RM

Spinrad, J

Tucker, A

机构：

[1] Univ Chile, Fac Ciencias Fis & Matemat, Dept Ingn Ind, Santiago, Chile

[2] Univ Buenos Aires, Fac Ciencias Exactas & Nat, Dept Computac, Buenos Aires, DF, Argentina

[3] Colorado State Univ, Dept Comp Sci, Ft Collins, CO 80528 USA

[4] Vanderbilt Univ, Dept Elect Engn & Comp Sci, Nashville, TN 37235 USA

[5] SUNY Stony Brook, Dept Appl Math, Stony Brook, NY 11794 USA

来源：

JOURNAL OF ALGORITHMS-COGNITION INFORMATICS AND LOGIC | 2006年 / 58卷 / 01期

关键词：

circular-arc graphs; graph algorithms; polynomial recognition; proper circular-arc graphs; unit circular-arc graphs;

D O I：

10.1016/j.jalgor.2004.08.003

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We present an efficient algorithm for recognizing unit circular-arc (UCA) graphs, based on a characterization theorem for UCA graphs proved by Tucker in the seventies. Given a proper circular-arc (PCA) graph G, the algorithm starts from a PCA model for G, removes all its circle-covering pairs of arcs and determines whether G is a UCA graph. We also give an O(N) time bound for Tucker's 3/2-approximation algorithm for coloring circular-arc graphs with N vertices, when a circular-arc model is given. (C) 2004 Elsevier Inc. All rights reserved.

引用

页码：67 / 78

页数：12

共 18 条

[1]

Cormen T. H., 2001, Introduction to Algorithms, V2nd

[2] Linear-time representation algorithms for proper circular-arc graphs and proper interval graphs [J].