Navegar

Colección

Datos Estadísticas

Artículo

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:

In a recent paper, Duran et al. [J. Algorithms, 58 (2006), pp. 67-78] described an algorithm of complexity O(n2) for recognizing whether a graph G with n vertices and m edges 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 UCA 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, based on network circulations. The characterization leads to a different recognition algorithm and to answering these questions in the affirmative. We construct a UCA model whose extremes of the arcs correspond to integers of size O(n). The proposed algorithms, for recognizing UCA graphs and constructing UCA models, have complexities O(n + m). Furthermore, the complexities reduce to O(n), if a proper circular-arc (PCA) model of G is already given as the input, provided the extremes of the arcs are ordered. We remark that a PCA model of G can be constructed in O(n + m) time, using the algorithm by Deng, Hell, and Huang [SIAM J. Comput., 25 (1996), pp. 390-403]. Finally, we also describe a linear time algorithm for finding feasible circulations in networks with nonnegative lower capacities and unbounded upper capacities. Such an algorithm is employed in the model construction for UCA graphs. © 2008 Society for Industrial and Applied Mathematics.

Registro:

Documento: Artículo
Título:Unit circular-arc graph representations and feasible circulations
Autor:Lin, M.C.; Szwarcfiter, J.L.
Filiación:Departamento de Computación, Universidad de Buenos Aires, Facultad de Ciencias Exactas y Naturales, Buenos Aires 1428, Argentina
Universidade Federal do Rio de Janeiro, Instituto de Matemática, NCE and COPPE, Caixa Postal 2324, 20001-970 Rio de Janeiro, Brazil
Palabras clave:Algorithm; Circular-arc graph; Circular-arc model; Circulations; Networks; Proper circular-arc graph; Unit circular-arc graph; Algorithms; Cavity resonators; Graph theory; Paper; Polynomial approximation; Circular-arc graph; Circular-arc model; Circulations; Networks; Proper circular-arc graph; Unit circular-arc graph; Mathematical models
Año:2008
Volumen:22
Número:1
Página de inicio:409
Página de fin:423
DOI: http://dx.doi.org/10.1137/060650805
Título revista:SIAM Journal on Discrete Mathematics
Título revista abreviado:SIAM J Discrete Math
ISSN:08954801
CODEN:SJDME
Registro:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_08954801_v22_n1_p409_Lin

Referencias:

  • DENG, X., HELL, P., HUANG, J., Linear time representation algorithms for proper circulararc graphs and proper interval graphs (1996) SIAM J. Comput, 25, pp. 390-403
  • DURAN, G., GRAVANO, A., MCCONNELL, R.M., SPINRAD, J.P., TUCKER, A., Polynomial time recognition of unit circular-arc graphs (2006) J. Algorithms, 58, pp. 67-78
  • ESCHEN, E., SPINRAD, J.P., An O(n 2) algorithm for circular-arc graph recognition (1993) Proceedings of the 4th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 128-137. , Austin, TX, ACM, New York, SIAM, Philadelphia
  • GOLUMBIC, M.C., (1980) Algorithmic Graph Theory and Perfect Graphs, , Academic Press, New York
  • HOFFMAN, A.J., Some recent applications of the theory of linear inequalities to extremal combinatorial analysis (1960) Proceedings of the Symposia in Applied Mathematics, pp. 113-117. , American Mathematical Society, Providence, RI
  • HSU, W.L., O(mn) algorithms for the recognition and isomorphism problems on circular-arc graphs (1995) SIAM J. Comput, 24, pp. 411-439
  • LIN, M.C., SZWARCFITER, J.L., Efficient construction of unit circular-arc models (2006) Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 309-315. , Miami, FL
  • MCCONNELL, R.M., Linear-time recognition of circular-arc graphs (2003) Algorithmica, 37, pp. 93-147
  • SCHRIJVER, A., Combinatorial Optimization (2003) Polyhedra and Efficiency, A. , Springer-Verlag, Berlin
  • SPINRAD, J.P., (2003) Efficient Graph Representations, Fields Institute Monographs, 19. , AMS, Providence, RI
  • TARJAN, R.E., Depth-first search and linear graph algorithms (1972) SIAM J. Comput, 1, pp. 146-160
  • TUCKER, A., Characterizing circular-arc graphs (1970) Bull. Amer. Math. Soc, 76, pp. 1257-1260
  • TUCKER, A., Structure theorems for some circular-arc graphs (1974) Discrete Math, 7, pp. 167-195
  • TUCKER, A., An efficient test for circular-arc graphs (1980) SIAM J. Comput, 9, pp. 1-24

Citas:

---------- APA ----------
Lin, M.C. & Szwarcfiter, J.L. (2008) . Unit circular-arc graph representations and feasible circulations. SIAM Journal on Discrete Mathematics, 22(1), 409-423.
http://dx.doi.org/10.1137/060650805
---------- CHICAGO ----------
Lin, M.C., Szwarcfiter, J.L. "Unit circular-arc graph representations and feasible circulations" . SIAM Journal on Discrete Mathematics 22, no. 1 (2008) : 409-423.
http://dx.doi.org/10.1137/060650805
---------- MLA ----------
Lin, M.C., Szwarcfiter, J.L. "Unit circular-arc graph representations and feasible circulations" . SIAM Journal on Discrete Mathematics, vol. 22, no. 1, 2008, pp. 409-423.
http://dx.doi.org/10.1137/060650805
---------- VANCOUVER ----------
Lin, M.C., Szwarcfiter, J.L. Unit circular-arc graph representations and feasible circulations. SIAM J Discrete Math. 2008;22(1):409-423.
http://dx.doi.org/10.1137/060650805