Navegar

Colección

Datos Estadísticas

Artículo

Durán, G.; Gravano, A.; McConnell, R.M.; Spinrad, J.; Tucker, A. "Polynomial time recognition of unit circular-arc graphs" (2006) Journal of Algorithms. 58(1):67-78
La versión final de este artículo es de uso interno de la institución.
Consulte el artículo en la página del editor
Consulte la política de Acceso Abierto del editor

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