Polynomial time recognition of unit circular-arc graphs

Guillermo Durán; Agustín Gravano; Ross M. McConnell; Jeremy Spinrad; Alan Tucker

doi:10.1016/j.jalgor.2004.08.003

Polynomial time recognition of unit circular-arc graphs

Guillermo Durán
, Agustín Gravano
, Ross M. McConnell
, Jeremy Spinrad
, Alan Tucker

Applied Mathematics and Statistics

Universidad de Chile
Universidad de Buenos Aires
Colorado State University
Vanderbilt University

Research output: Contribution to journal › Article › peer-review

15 Scopus citations

Abstract

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.

Original language	English
Pages (from-to)	67-78
Number of pages	12
Journal	Journal of Algorithms
Volume	58
Issue number	1
DOIs	https://doi.org/10.1016/j.jalgor.2004.08.003
State	Published - Jan 2006

Keywords

Circular-arc graphs
Graph algorithms
Polynomial recognition
Proper circular-arc graphs
Unit circular-arc graphs

Access to Document

10.1016/j.jalgor.2004.08.003

Cite this

@article{600eabbb948f4c00a77c25a555bfc1f1,

title = "Polynomial time recognition of unit circular-arc graphs",

abstract = "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.",

keywords = "Circular-arc graphs, Graph algorithms, Polynomial recognition, Proper circular-arc graphs, Unit circular-arc graphs",

author = "Guillermo Dur{\'a}n and Agust{\'i}n Gravano and McConnell, \{Ross M.\} and Jeremy Spinrad and Alan Tucker",

year = "2006",

month = jan,

doi = "10.1016/j.jalgor.2004.08.003",

language = "English",

volume = "58",

pages = "67--78",

journal = "Journal of Algorithms",

issn = "0196-6774",

number = "1",

}

TY - JOUR

T1 - Polynomial time recognition of unit circular-arc graphs

AU - Durán, Guillermo

AU - Gravano, Agustín

AU - McConnell, Ross M.

AU - Spinrad, Jeremy

AU - Tucker, Alan

PY - 2006/1

Y1 - 2006/1

N2 - 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.

AB - 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.

KW - Circular-arc graphs

KW - Graph algorithms

KW - Polynomial recognition

KW - Proper circular-arc graphs

KW - Unit circular-arc graphs

UR - https://www.scopus.com/pages/publications/28444481676

U2 - 10.1016/j.jalgor.2004.08.003

DO - 10.1016/j.jalgor.2004.08.003

M3 - Article

AN - SCOPUS:28444481676

SN - 0196-6774

VL - 58

SP - 67

EP - 78

JO - Journal of Algorithms

JF - Journal of Algorithms

IS - 1

ER -

Polynomial time recognition of unit circular-arc graphs

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this