Paper Info
Title
Efficient construction of unit circular-arc models
Abstract
In a recent paper, Durán, Gravano, McConnell, Spinrad and Tucker described an algorithm of complexity O(n2) for recognizing whether a graph G with n vertices is a unit circular-arc (UCA) graph. Furthermore the following open questions were posed in the above paper: (i) Is it possible to construct a UCA model for G in polynomial time? (ii) Is it possible to construct a model, whose extremes of the arcs correspond to integers of polynomial size? (iii) If (ii) is true, could such a model be constructed in polynomial time? In the present paper, we describe a characterization of UCA graphs which leads to linear time algorithms for recognizing UCA graphs and constructing UCA models. Furthermore, we construct models whose extreme of the arcs correspond to integers of size O(n). The proposed algorithms provide positive answers to the three above questions.
Year
DOI
Venue
2006
10.1145/1109557.1109592
SODA
Keywords
Field
DocType
uca graph,unit circular-arc model,linear time algorithm,uca model,size o,recent paper,present paper,complexity o,graph g,polynomial time,polynomial size,efficient construction,nucleolus,np hard
Flow game,Integer,Discrete mathematics,Graph,Combinatorics,Arc (geometry),Vertex (geometry),Polynomial,Time complexity,Mathematics
Conference
ISBN
Citations 
PageRank 
0-89871-605-5
9
0.73
References 
Authors
7
2
Name
Order
Citations
PageRank
Min Chih Lin125921.22
Jayme L. Szwarcfiter254645.97