Artículo
Lin, M.C.; Soulignac, F.J.; Szwarcfiter, J.L. "Proper Helly circular-arc graphs" (2007) 33rd International Conference Workshop on Graph-Theoretic Concepts in Computer Science, WG 2007. 4769 LNCS:248-257
Consulte la política de Acceso Abierto del editor
Abstract:
A circular-arc model M = (C, A) is a circle C together with a collection A of arcs of C. If no arc is contained in any other then M is a proper circular-arc model, if every arc has the same length then M is a unit circular-arc model and if A satisfies the Helly Property then M is a Helly circular-arc model. A (proper) (unit) (Helly) circular-arc graph is the intersection graph of the arcs of a (proper) (Helly) circular-arc model. Circular-arc graphs and their subclasses have been the object of a great deal of attention in the literature. Linear time recognition algorithms have been described both for the general class and for some of its subclasses. In this article we study the circular-arc graphs which admit a model which is simultaneously proper and Helly. We describe characterizations for this class, including one by forbidden induced subgraphs. These characterizations lead to linear time certifying algorithms for recognizing such graphs. Furthermore, we extend the results to graphs which admit a model which is simultaneously unit and Helly, also leading to characterizations and a linear time certifying algorithm. © Springer-Verlag Berlin Heidelberg 2007.
Registro:
| Documento: | Artículo |
| Título: | Proper Helly circular-arc graphs |
| Autor: | Lin, M.C.; Soulignac, F.J.; Szwarcfiter, J.L. |
| Ciudad: | Dornburg |
| 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, Inst. de Matemática, NCE and COPPE, Caixa Postal 2324, 20001-970 Rio de Janeiro, RJ, Brazil |
| Palabras clave: | Algorithms; Forbidden subgraphs; Helly circular-arc graphs; Proper circular-arc graphs; Unit circular-arc graphs; Algorithms; Linear programming; Mathematical models; Forbidden subgraphs; Helly circular-arc graphs; Proper circular-arc graphs; Unit circular-arc graphs; Graph theory |
| Año: | 2007 |
| Volumen: | 4769 LNCS |
| Página de inicio: | 248 |
| Página de fin: | 257 |
| Título revista: | 33rd International Conference Workshop on Graph-Theoretic Concepts in Computer Science, WG 2007 |
| Título revista abreviado: | Lect. Notes Comput. Sci. |
| ISSN: | 03029743 |
| Registro: | https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03029743_v4769LNCS_n_p248_Lin |
Referencias:
- Brandstädt, A., Le, V., Spinrad, J., (1999) Graph Classes: A Survey, , SIAM, Philadelphia
- Deng, X., Hell, P., Huang, J., Linear time representation algorithms for proper circular-arc graphs and proper interval graphs (1996) SIAM Journal on Computing, 25, pp. 390-403
- Golumbic, M., (1980) Algorithmic Graph Theory and Perfect Graphs, , Academic Press, London
- Joeris, B., Lin, M.C., McConnell, R.M., Spinrad, J., Szwarcfiter, J.L.: Linear time recognition of Helly circular-arc models and graphs, (manuscript, 2007) (Presented at COCOON 2006 and SIAM DM 2006 Confs.); Kaplan, H., Nussbaum, Y.: Certifying algorithms for recognizing proper circulararc graphs and unit circular-arc graphs. In: Fomin, F.V. (ed.) WG 2006. LNCS, 4271, pp. 289-300. Springer, Heidelberg (2006); Kaplan, H., Nussbaum, Y.: A simpler linear-time recognition of circular-arc graphs. In: Arge, L., Freivalds, R. (eds.) SWAT 2006. LNCS, 4059, pp. 41-52. Springer, Heidelberg (2006); Lin, M.C., Szwarcfiter, J.L., Efficient construction of unit circular-arc models (2006) SODA 2006. Proceedings of the 17th ACM-SIAM Symposium on Discrete Algorithms, pp. 309-315
- Lin, M.C., McConnell, R.M., Soulignac, F.J., Szwarcfiter, J.L., On cliques of Helly circular-arc graphs, , in preparation
- McConnell, R.M., Linear-time recognition of circular-arc graphs (2001) FOCS 2001. Proceedings of the 42nd Annual IEEE Symposium on Foundations of Computer Science, pp. 386-394
- McConnell, R.M., Linear-time recognition of circular-arc graphs (2003) Algorithmica, 37 (2), pp. 93-147
- McConnell, R.M., A certifying algorithm for the consecutive ones property (2004) SODA 2004. Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 716-770
- Spinrad, J., (2003) Efficient Graph Representations, , American Mathematical Society, Providence, Rhode Island
- Tucker, A., Matrix characterizations of circular-arc graphs (1971) Pacific Journal of Mathematics, 38, pp. 535-545
- Tucker, A., Structure theorems for some circular-arc graphs (1974) Discrete Mathematics, 7, pp. 167-195
Citas:
---------- APA ----------
Lin, M.C., Soulignac, F.J. & Szwarcfiter, J.L. (2007) . Proper Helly circular-arc graphs. 33rd International Conference Workshop on Graph-Theoretic Concepts in Computer Science, WG 2007, 4769 LNCS, 248-257.Recuperado de https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03029743_v4769LNCS_n_p248_Lin [ ]
---------- CHICAGO ----------
Lin, M.C., Soulignac, F.J., Szwarcfiter, J.L. "Proper Helly circular-arc graphs" . 33rd International Conference Workshop on Graph-Theoretic Concepts in Computer Science, WG 2007 4769 LNCS (2007) : 248-257.Recuperado de https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03029743_v4769LNCS_n_p248_Lin [ ]
---------- MLA ----------
Lin, M.C., Soulignac, F.J., Szwarcfiter, J.L. "Proper Helly circular-arc graphs" . 33rd International Conference Workshop on Graph-Theoretic Concepts in Computer Science, WG 2007, vol. 4769 LNCS, 2007, pp. 248-257.Recuperado de https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03029743_v4769LNCS_n_p248_Lin [ ]
---------- VANCOUVER ----------
Lin, M.C., Soulignac, F.J., Szwarcfiter, J.L. Proper Helly circular-arc graphs. Lect. Notes Comput. Sci. 2007;4769 LNCS:248-257.Available from: https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03029743_v4769LNCS_n_p248_Lin [ ]
