Navegar

Colección

Datos Estadísticas

Artículo

Lin, M.C.; McConnell, R.M.; Soulignac, F.J.; Szwarcfiter, J.L. "On cliques of Helly Circular-arc Graphs" (2008) Electronic Notes in Discrete Mathematics. 30(C):117-122
La versión final de este artículo es de uso interno. El editor solo permite incluir en el repositorio el artículo en su versión post-print. Por favor, si usted la posee enviela a
Consulte el artículo en la página del editor
Consulte la política de Acceso Abierto del editor

Abstract:

A circular-arc graph is the intersection graph of a set of arcs on the circle. It is a Helly circular-arc graph if it has a Helly model, where every maximal clique is the set of arcs that traverse some clique point on the circle. A clique model is a Helly model that identifies one clique point for each maximal clique. A Helly circular-arc graph is proper if it has a Helly model where no arc is a subset of another. In this paper, we show that the clique intersection graphs of Helly circular-arc graphs are related to the proper Helly circular-arc graphs. This yields the first polynomial (linear) time recognition algorithm for the clique graphs of Helly circular-arc graphs. Next, we develop an O (n) time algorithm to obtain a clique model of Helly model, improving the previous O (n2) bound. This gives a linear-time algorithm to find a proper Helly model for the clique graph of a Helly circular-arc graph. As an application, we find a maximum weighted clique of a Helly circular-arc graph in linear time. © 2008 Elsevier B.V. All rights reserved.

Registro:

Documento: Artículo
Título:On cliques of Helly Circular-arc Graphs
Autor:Lin, M.C.; McConnell, R.M.; Soulignac, F.J.; Szwarcfiter, J.L.
Filiación:Departamento de Computación, FCEN, Universidad de Buenos Aires, Buenos Aires, Argentina
Computer Science Department, Colorado State University, Fort Collins, CO 80523-1873, United States
Universidade Federal do Rio de Janeiro, Inst. de Matemática, NCE, Caixa Postal 2324, 20001-970 Rio de Janeiro, RJ, Brazil
Palabras clave:algorithms; clique graphs; Helly circular-arc graphs; maximum weight cliques; proper Helly circular-arc graphs
Año:2008
Volumen:30
Número:C
Página de inicio:117
Página de fin:122
DOI: http://dx.doi.org/10.1016/j.endm.2008.01.020
Título revista:Electronic Notes in Discrete Mathematics
Título revista abreviado:Electron. Notes Discrete Math.
ISSN:15710653
Registro:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_15710653_v30_nC_p117_Lin

Referencias:

  • Alcón, L., Faria, L., Figueiredo, C., Gutiérrez, M., Clique graph recognition is NP-complete (2006) LNCS, 4271, pp. 269-277. , Proc. of WG 2006
  • Brandstädt, A., Le, V., Spinrad, J., (1999) Graph Classes: A Survey, , SIAM
  • Durán, G., Lin, M., Clique graphs of Helly circular-arc graphs (2001) Ars Combin., 60, pp. 255-271
  • Durán, G., Lin, M., Mera, S., Szwarcfiter, J., Algorithms for clique-independent sets on subclasses of circular-arc graphs (2006) Discrete Appl. Math., 154, pp. 1783-1790
  • Hamelink, R., A partial characterization of clique graphs (1968) J. Combin. Theory Ser. B, 5, pp. 192-197
  • Lin, M., and J. Szwarcfiter, Characterizations and recognition of circular-arc graphs and subclasses: a survey, manuscript, 2006; Lin, M., F. Soulignac and J. Szwarcfiter, Proper Helly circular-arc graphs, Proc. of WG 2007 (2007), to appear; Roberts, F., Spencer, J., A characterization of clique graphs (1971) J. Combin. Theory Ser. B, 10, pp. 102-108
  • Shih, W., Hsu, W., An O (n log n + m log log n) algorithm for finding a maximum weight clique in circular-arc graphs (1989) Inform. Process. Lett., 31, pp. 129-134
  • Spinrad, J., (2003) Efficient Graph Representations, , Amer. Math. Soc
  • Szwarcfiter, J., A survey on Clique Graphs, in: "Recent Advances in Algorithms and Combinatorics", Springer, 109-136

Citas:

---------- APA ----------
Lin, M.C., McConnell, R.M., Soulignac, F.J. & Szwarcfiter, J.L. (2008) . On cliques of Helly Circular-arc Graphs. Electronic Notes in Discrete Mathematics, 30(C), 117-122.
http://dx.doi.org/10.1016/j.endm.2008.01.020
---------- CHICAGO ----------
Lin, M.C., McConnell, R.M., Soulignac, F.J., Szwarcfiter, J.L. "On cliques of Helly Circular-arc Graphs" . Electronic Notes in Discrete Mathematics 30, no. C (2008) : 117-122.
http://dx.doi.org/10.1016/j.endm.2008.01.020
---------- MLA ----------
Lin, M.C., McConnell, R.M., Soulignac, F.J., Szwarcfiter, J.L. "On cliques of Helly Circular-arc Graphs" . Electronic Notes in Discrete Mathematics, vol. 30, no. C, 2008, pp. 117-122.
http://dx.doi.org/10.1016/j.endm.2008.01.020
---------- VANCOUVER ----------
Lin, M.C., McConnell, R.M., Soulignac, F.J., Szwarcfiter, J.L. On cliques of Helly Circular-arc Graphs. Electron. Notes Discrete Math. 2008;30(C):117-122.
http://dx.doi.org/10.1016/j.endm.2008.01.020