INVESTIGADORES
LIN Min Chih
congresos y reuniones científicas
Título:
Efficient Construction of Unit Circular-Arc Models
Autor/es:
MIN CHIH LIN; JAYME L. SZWARCFITER
Lugar:
MIAMI, EEUU
Reunión:
Conferencia; SODA'06 (ACM-SIAM Symposium on Discrete Algorithms); 2006
Institución organizadora:
ACM Special Interest Group on Algorithms and Computation Theory and SIAM Activity Group on Discrete Mathematics
Resumen:
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.