Navegar

Colección

Datos Estadísticas

Artículo

Este artículo es de Acceso Abierto y puede ser descargado en su versión final desde nuestro repositorio
Consulte el artículo en la página del editor
Consulte la política de Acceso Abierto del editor

Registro:

Documento: Artículo
Título:Algorithms for clique-independent sets on subclasses of circular-arc graphs
Autor:Durán, G.; Lin, M.C.; Mera, S.; Szwarcfiter, J.L.
Filiación:Departamento de Ingeniería Industrial, Facultad de Ciencias Físicas y Matemáticas, Universidad de Chile, Santiago, Chile
Departamento de Computación, Facultad de Ciencias Exactas y Naturales, Universidad de Buenos Aires, Buenos Aires, Argentina
Instituto de Matemática, NCE, COPPE, Rio de Janeiro, Brazil
Palabras clave:Algorithms; Circular-arc graphs; Clique-independent sets; Helly circular-arc graphs; Algorithms; Computational complexity; Computational methods; Mathematical models; Set theory; Circular-arc graphs; Clique-independent sets; Helly circular-arc graphs; Graph theory
Año:2006
Volumen:154
Número:13 SPEC ISS
Página de inicio:1783
Página de fin:1790
DOI: http://dx.doi.org/10.1016/j.dam.2006.03.022
Título revista:Discrete Applied Mathematics
Título revista abreviado:Discrete Appl Math
ISSN:0166218X
CODEN:DAMAD
PDF:https://bibliotecadigital.exactas.uba.ar/download/paper/paper_0166218X_v154_n13SPECISS_p1783_Duran.pdf
Registro:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_0166218X_v154_n13SPECISS_p1783_Duran

Referencias:

  • Balachandran, V., Nagavamsi, P., Pandu Rangan, C., Clique transversal and clique independence on comparability graphs (1996) Inform. Process. Lett., 58, pp. 181-184
  • Bonomo, F., Self-clique Helly circular-arc graphs (2006) Discrete Math., 306 (6), pp. 595-597
  • Bonomo, F., Durán, G., Lin, M.C., Szwarcfiter, J.L., On balanced graphs (2006) Math. Programming, 105, pp. 233-250
  • Brandstädt, A., Chepoi, V.D., Dragan, F.F., Voloshin, V.I., Dually chordal graphs (1998) SIAM J. Discrete Math., 11, pp. 109-127
  • Chang, G.J., Farber, M., Tuza, Zs., Algorithmic aspects of neighbourhood numbers (1993) SIAM J. Discrete Math., 6, pp. 24-29
  • Dahlhaus, E., Manuel, P.D., Miller, M., Maximum h-colourable subgraph problem in balanced graphs (1998) Inform. Process. Lett., 65, pp. 301-303
  • Duffus, D., Kiersted, H.A., Trotter, W.T., Fibers and ordered set coloring (1991) J. Combin. Theory A, 58, pp. 158-164
  • Durán, G., Lin, M.C., Clique graphs of Helly circular-arc graphs (2001) Ars Combin., 60, pp. 255-271
  • Durán, G., Lin, M.C., Mera, S., Szwarcfiter, J.L., Clique-independent sets of Helly circular-arc graphs (2004) Electr. Notes Discrete Math., 18, pp. 41-46
  • Durán, G., Lin, M.C., Szwarcfiter, J.L., On clique-transversals and clique-independent sets (2002) Ann. Oper. Res., 116, pp. 71-77
  • Gavril, F., Algorithms on circular-arc graphs (1974) Networks, 4, pp. 357-369
  • Golumbic, M.C., (1980) Algorithmic Graph Theory and Perfect Graphs, , Academic Press, New York
  • Golumbic, M.C., Hammer, P., Stability in circular-arc graphs (1988) J. Algorithms, 9, pp. 314-320
  • Guruswami, V., Pandu Rangan, C., Algorithmic aspects of clique transversals and clique independent sets (2000) Discrete Appl. Math., 100, pp. 183-202
  • Hsu, W.L., Tsai, K.H., Linear time algorithms on circular-arc graphs (1991) Inform. Process. Lett., 40, pp. 123-129
  • McConnell, R.M., Linear-time recognition of circular-arc graphs (2003) Algorithmica, 37, pp. 93-147
  • Shih, W.K., Hsu, W.L., An O (n log n + m log log n) algorithm for finding a maximum weight clique in circular-arc graphs (1989) Inform. Process. Lett., 32, pp. 129-134
  • Spinrad, J.P., (2003) Efficient Graph Representation, Fields Institute Monographs, , American Mathematical Society, Providence, RI
  • Tucker, A., Characterizing circular-arc graphs (1970) Bull. Amer. Math. Soc., 76, pp. 1257-1260
  • Tucker, A., An efficient test for circular-arc graphs (1980) SIAM J. Comput., 9, pp. 1-24

Citas:

---------- APA ----------
Durán, G., Lin, M.C., Mera, S. & Szwarcfiter, J.L. (2006) . Algorithms for clique-independent sets on subclasses of circular-arc graphs. Discrete Applied Mathematics, 154(13 SPEC ISS), 1783-1790.
http://dx.doi.org/10.1016/j.dam.2006.03.022
---------- CHICAGO ----------
Durán, G., Lin, M.C., Mera, S., Szwarcfiter, J.L. "Algorithms for clique-independent sets on subclasses of circular-arc graphs" . Discrete Applied Mathematics 154, no. 13 SPEC ISS (2006) : 1783-1790.
http://dx.doi.org/10.1016/j.dam.2006.03.022
---------- MLA ----------
Durán, G., Lin, M.C., Mera, S., Szwarcfiter, J.L. "Algorithms for clique-independent sets on subclasses of circular-arc graphs" . Discrete Applied Mathematics, vol. 154, no. 13 SPEC ISS, 2006, pp. 1783-1790.
http://dx.doi.org/10.1016/j.dam.2006.03.022
---------- VANCOUVER ----------
Durán, G., Lin, M.C., Mera, S., Szwarcfiter, J.L. Algorithms for clique-independent sets on subclasses of circular-arc graphs. Discrete Appl Math. 2006;154(13 SPEC ISS):1783-1790.
http://dx.doi.org/10.1016/j.dam.2006.03.022