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.
Registro:
| Documento: |
Conferencia
|
| Título: | Efficient construction of unit circular-arc models |
| Autor: | Lin, M.C.; Szwarcfiter, J.L. |
| Ciudad: | Miami, FL |
| Filiación: | Universidad de Buenos Aires, Facultad de Ciencias Exactas y Naturales, Departamento de Computación, Buenos Aires, Argentina
Universidade Federal do Rio de Janeiro, Instituto de Matemática, COPPE, Caixa Postal 2324, 20001-970 Rio de Janeiro, RJ, Brazil
|
| Palabras clave: | Algorithms; Graph theory; Polynomials; Time series analysis; Circular-arc models; Integers; Vertices; Mathematical models |
| Año: | 2006
|
| Página de inicio: | 309
|
| Página de fin: | 315
|
| Título revista: | Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms
|
| Título revista abreviado: | Proc Annu ACM SIAM Symp Discrete Algorithms
|
| CODEN: | PAAAF
|
| Registro: | https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_NIS07298_v_n_p309_Lin |
Referencias:
- Deng, X., Hell, P., Huang, J., Linear time representation algorithms for proper circular-arc graphs and proper interval graphs (1996) SIAM J. Computing, 25, pp. 390-403
- Durán, G., Gravano, A., McConnell, R.M., Spinrad, J.P., Tucker, A., Polynomial time recognition of unit circular-arc graphs (2004) J. of Algorithms, , in press
- Eschen, E., Spinrad, J., An O(n2) algorithm for circular-arc graph recognition (1993) Proceedings of the 4th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 128-137
- Golumbic, M.C., (1980) Algorithmic Graph Theory and Perfect Graphs, , Academic Press, New York
- Hsu, W.L., O(mn) algorithms for the recognition and isomorphism problems on circular-arc graphs (1995) SIAM J. Computing, 24, pp. 411-439
- McConnell, R.M., Linear-time recognition of circulararc graphs (2003) Algorithmica, 37 (2), pp. 93-147
- Spinrad, J.P., (2003) Efficient Graph Representations, , Fields Institute Monographs, American Mathematical Society, Providence, Rhode Island
- Tucker, A., Characterizing circular-arc graphs (1970) Bull. American Mathematical Society, 76, pp. 1257-1260
- Tucker, A., Structure theorems for some circular-arc graphs (1974) Discrete Mathematics, 7, pp. 167-195
- Tucker, A., An efficient test for circular-arc graphs (1980) SIAM J. Computing, 9, pp. 1-24A4 - SIAM Activity Group on Discrete Mathematics; ACM Spec. Interest Group on Algorithms and Comput. Theory, SIGACT
Citas:
---------- APA ----------
Lin, M.C. & Szwarcfiter, J.L.
(2006)
. Efficient construction of unit circular-arc models. Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, 309-315.
Recuperado de https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_NIS07298_v_n_p309_Lin [ ]
---------- CHICAGO ----------
Lin, M.C., Szwarcfiter, J.L.
"Efficient construction of unit circular-arc models"
. Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms
(2006) : 309-315.
Recuperado de https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_NIS07298_v_n_p309_Lin [ ]
---------- MLA ----------
Lin, M.C., Szwarcfiter, J.L.
"Efficient construction of unit circular-arc models"
. Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2006, pp. 309-315.
Recuperado de https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_NIS07298_v_n_p309_Lin [ ]
---------- VANCOUVER ----------
Lin, M.C., Szwarcfiter, J.L. Efficient construction of unit circular-arc models. Proc Annu ACM SIAM Symp Discrete Algorithms. 2006:309-315.
Available from: https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_NIS07298_v_n_p309_Lin [ ]
