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. © 2004 Elsevier Inc. All rights reserved.
Registro:
Documento: |
Artículo
|
Título: | Polynomial time recognition of unit circular-arc graphs |
Autor: | Durán, G.; Gravano, A.; McConnell, R.M.; Spinrad, J.; Tucker, A. |
Filiación: | Departamento de Ingeniería Industrial, Facultad de Ciencias Físicas y Matemáticas, Universidad de Chile, Santiago, Chile Departamento de Computación, Facultad de Ciencias Exactas y Naturales, Universidad de Buenos Aires, Buenos Aires, Argentina Computer Science Department, Colorado State University, Fort Collins, CO 80528, United States Department of Electrical Engineering and Computer Science, Vanderbilt University, Nashville, TN 37235, United States Department of Applied Mathematics, State University of New York at Stony Brook, Stony Brook, NY 11794-3600, United States
|
Palabras clave: | Circular-arc graphs; Graph algorithms; Polynomial recognition; Proper circular-arc graphs; Unit circular-arc graphs; Approximation theory; Graph theory; Mathematical models; Polynomials; Principal component analysis; Theorem proving; Circular-arc graphs; Graph algorithms; Polynomial recognition; Proper circular-arc graphs; Unit circular-arc graphs; Algorithms |
Año: | 2006
|
Volumen: | 58
|
Número: | 1
|
Página de inicio: | 67
|
Página de fin: | 78
|
DOI: |
http://dx.doi.org/10.1016/j.jalgor.2004.08.003 |
Título revista: | Journal of Algorithms
|
Título revista abreviado: | J Algorithms
|
ISSN: | 01966774
|
CODEN: | JOALD
|
Registro: | https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_01966774_v58_n1_p67_Duran |
Referencias:
- Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C., (2001) Introduction to Algorithms, , McGraw-Hill Boston
- Deng, X., Hell, P., Huang, J., Linear time representation algorithms for proper circular-arc graphs and proper interval graphs (1996) SIAM J. Comput., 25, pp. 390-403
- Durán, G., Lin, M., On some subclasses of circular-arc graphs (2000) Congressus Numerantium, 146, pp. 201-212
- Gavril, F., Algorithms on circular-arc graphs (1974) Networks, 4, pp. 357-369
- Gabow, H.N., Tarjan, R.E., A linear time algorithm for a special case of disjoint set union (1985) J. Comput. System Sci., 30, pp. 209-221
- Golumbic, M., (1980) Algorithm Graph Theory and Perfect Graphs, , Academic Press New York
- Gustedt, J., Efficient union-find for planar graphs and other sparse graph classes (1998) Theoret. Comput. Sci., 203, pp. 123-141
- Hubert, L., Some applications of graph theory and related non-metric techniques to problems of approximate seriation: The case of symmetry proximity measures (1974) British J. Math. Statist. Psych., 27, pp. 133-153
- McConnell, R.M., Linear-time recognition of circular-arc graphs (2003) Algorithmica, 37 (2), pp. 93-147
- Spinrad, J., (1997) Representations of Graphs, , book manuscript
- Stahl, F., Circular genetic maps (1967) J. Cell Physiol., 70 (1), pp. 1-12
- Stouffers, K., Scheduling of traffic lights - A new approach (1968) Transportation Res., 2, pp. 199-234
- Tucker, A., Characterizing circular-arc graphs (1970) Bull. Amer. Math. Soc., 76, pp. 1257-1260
- Tucker, A., Matrix characterizations of circular-arc graphs (1971) Pacific J. Math., 38, pp. 535-545
- Tucker, A., Structure theorems for some circular-arc graphs (1974) Discrete Math., 7, pp. 167-195
- Tucker, A., Coloring a family of circular-arc graphs (1975) SIAM J. Appl. Math., 29, pp. 493-502
- Tucker, A., An efficient test for circular-arc graphs (1980) SIAM J. Comput., 9, pp. 1-24
- Valencia-Pabon, M., Revisiting Tucker's algorithm to color circular arc graphs (2003) SIAM J. Comput., 32, pp. 1067-1072
Citas:
---------- APA ----------
Durán, G., Gravano, A., McConnell, R.M., Spinrad, J. & Tucker, A.
(2006)
. Polynomial time recognition of unit circular-arc graphs. Journal of Algorithms, 58(1), 67-78.
http://dx.doi.org/10.1016/j.jalgor.2004.08.003---------- CHICAGO ----------
Durán, G., Gravano, A., McConnell, R.M., Spinrad, J., Tucker, A.
"Polynomial time recognition of unit circular-arc graphs"
. Journal of Algorithms 58, no. 1
(2006) : 67-78.
http://dx.doi.org/10.1016/j.jalgor.2004.08.003---------- MLA ----------
Durán, G., Gravano, A., McConnell, R.M., Spinrad, J., Tucker, A.
"Polynomial time recognition of unit circular-arc graphs"
. Journal of Algorithms, vol. 58, no. 1, 2006, pp. 67-78.
http://dx.doi.org/10.1016/j.jalgor.2004.08.003---------- VANCOUVER ----------
Durán, G., Gravano, A., McConnell, R.M., Spinrad, J., Tucker, A. Polynomial time recognition of unit circular-arc graphs. J Algorithms. 2006;58(1):67-78.
http://dx.doi.org/10.1016/j.jalgor.2004.08.003