Navegar

Colección

Datos Estadísticas

Artículo

Barrionuevo, J.M.; Calvo, A.; Durán, G.; Protti, F. "New advances about a conjecture on Helly circle graphs" (2004) Electronic Notes in Discrete Mathematics. 18:31-36
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 circle graph is the intersection graph of a set of chords on a circle. A graph is Helly circle if there is a model of chords satisfying the Helly property. In 2003 it was conjectured that Helly circle graphs are exactly diamond-free circle graphs. In this work, we propose a method to compress any Helly circle representation of a graph and give some ideas to advance in an inductive proof of the diamond conjecture. © 2004 Elsevier B.V. All rights reserved.

Registro:

Documento: Artículo
Título:New advances about a conjecture on Helly circle graphs
Autor:Barrionuevo, J.M.; Calvo, A.; Durán, G.; Protti, F.
Filiación:Departamento de Computación, Facultad de Ciencias Exactas y Naturales, Universidad de Buenos Aires, Buenos Aires, Argentina
Departamento de Ingeniería Industrial, Facultad de Ciencias Físicas y Matemáticas, Universidad de Chile, Santiago, Chile
IM and NCE, Universidade Federal do Rio de Janeiro, Rio de Janeiro, Brazil
Palabras clave:circle graphs; compression; diamond; Helly circle graphs
Año:2004
Volumen:18
Página de inicio:31
Página de fin:36
DOI: http://dx.doi.org/10.1016/j.endm.2004.06.005
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_v18_n_p31_Barrionuevo

Referencias:

  • Bouchet, A., Reducing prime graphs and recognizing circle graphs (1987) Combinatorica, 7 (3), pp. 243-254
  • Durán, G., Some new results on circle graphs (2003) Matemática Contemporánea, 25, pp. 91-106
  • Durán, G., Gravano, A., Groshaus, M., Protti, F., Szwarcfiter, J., On a conjecture concerning Helly circle graphs (2003) Pesquisa Operacional, 23 (1), pp. 221-229
  • Even, S., Itai, A., Queues, stacks and graphs (1971) Theory of Machines and Computations, pp. 71-86. , Kohavi A., and Paz A. (Eds), Acad. Press
  • Gabor, C., Supowit, K., Hsu, W., Recognizing circle graphs in polynomial time (1989) Journal of the ACM, 36 (3), pp. 435-473
  • Knuth, D., (1969) The Art of Computer Programming Vol. 1, , Addison-Wesley
  • Naji, W., Reconnaissance des graphes de cordes (1985) Discrete Math., 54, pp. 329-337
  • Spinrad, J., Recognition of circle graphs (1994) Journal of Algorithms, 16 (2), pp. 264-282

Citas:

---------- APA ----------
Barrionuevo, J.M., Calvo, A., Durán, G. & Protti, F. (2004) . New advances about a conjecture on Helly circle graphs. Electronic Notes in Discrete Mathematics, 18, 31-36.
http://dx.doi.org/10.1016/j.endm.2004.06.005
---------- CHICAGO ----------
Barrionuevo, J.M., Calvo, A., Durán, G., Protti, F. "New advances about a conjecture on Helly circle graphs" . Electronic Notes in Discrete Mathematics 18 (2004) : 31-36.
http://dx.doi.org/10.1016/j.endm.2004.06.005
---------- MLA ----------
Barrionuevo, J.M., Calvo, A., Durán, G., Protti, F. "New advances about a conjecture on Helly circle graphs" . Electronic Notes in Discrete Mathematics, vol. 18, 2004, pp. 31-36.
http://dx.doi.org/10.1016/j.endm.2004.06.005
---------- VANCOUVER ----------
Barrionuevo, J.M., Calvo, A., Durán, G., Protti, F. New advances about a conjecture on Helly circle graphs. Electron. Notes Discrete Math. 2004;18:31-36.
http://dx.doi.org/10.1016/j.endm.2004.06.005