Navegar

Colección

Datos Estadísticas

Artículo

Durán, G.; Lin, M.C.; Mera, S.; Szwarcfiter, J.L. "Algorithms for finding clique-transversals of graphs" (2008) Annals of Operations Research. 157(1):37-45
Estamos trabajando para incorporar este artículo al repositorio
Consulte el artículo en la página del editor
Consulte la política de Acceso Abierto del editor

Abstract:

A clique-transversal of a graph G is a subset of vertices intersecting all the cliques of G. It is NP-hard to determine the minimum cardinality τ c of a clique-transversal of G. In this work, first we propose an algorithm for determining this parameter for a general graph, which runs in polynomial time, for fixed τ c . This algorithm is employed for finding the minimum cardinality clique-transversal of 3K2̄-free circular-arc graphs in O(n 4) time. Further we describe an algorithm for determining τ c of a Helly circular-arc graph in O(n) time. This represents an improvement over an existing algorithm by Guruswami and Pandu Rangan which requires O(n 2) time. Finally, the last proposed algorithm is modified, so as to solve the weighted version of the corresponding problem, in O(n 2) time. © 2007 Springer Science+Business Media, LLC.

Registro:

Documento: Artículo
Título:Algorithms for finding clique-transversals of graphs
Autor:Durán, G.; Lin, M.C.; Mera, S.; Szwarcfiter, J.L.
Filiación:Departamento de Ingeniería Industrial, Universidad de Chile, Santiago, Chile
Departamento de Computación, Universidad de Buenos Aires, Buenos Aires, Argentina
Universidade Federal do Rio de Janeiro, I. Matemática, NCE and COPPE, Caixa Postal 2324, Rio de Janeiro, RJ 20001-970, Brazil
Palabras clave:3K2̄-free circular-arc graphs; Algorithms; Circular-arc graphs; Clique-transversals; Helly circular-arc graphs
Año:2008
Volumen:157
Número:1
Página de inicio:37
Página de fin:45
DOI: http://dx.doi.org/10.1007/s10479-007-0189-x
Título revista:Annals of Operations Research
Título revista abreviado:Ann. Oper. Res.
ISSN:02545330
Registro:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_02545330_v157_n1_p37_Duran

Referencias:

  • Balachandran, V., Nagavamsi, P., Pandu Rangan, C., Clique transversal and clique independence on comparability graphs (1996) Information Processing Letters, 58, pp. 181-184
  • Bonomo, F., Durán, G., Lin, M.C., Szwarcfiter, J.L., On balanced graphs (2006) Mathematical Programming B, 105, pp. 233-250
  • Brandstädt, A., Chepoi, V.D., Dragan, F.F., Clique r-domination and clique r-packing problems on dually chordal graphs (1997) SIAM Journal on Discrete Mathematics, 10, pp. 109-127
  • Chang, G.J., Farber, M., Tuza, Z., Algorithmic aspects of neighbourhood numbers (1993) SIAM Journal on Discrete Mathematics, 6, pp. 24-29
  • Chang, M.S., Efficient algorithms for the domination problems on interval and circular-arc graphs (1998) SIAM Journal on Computing, 27, pp. 1671-1694
  • Chang, M.S., Chen, Y.H., Chang, G.J., Yan, J.H., Algorithmic aspects of the generalized clique-transversal problem on chordal graphs (1996) Discrete Applied Mathematics, 66, pp. 189-203
  • Dahlhaus, E., Manuel, P.D., Miller, M., Maximum h-colourable subgraph problem in balanced graphs (1998) Information Processing Letters, 65, pp. 301-303
  • Durán, G., Lin, M.L., Mera, S., Szwarcfiter, J.L., Algorithms for clique-independent sets on subclasses of circular-arc graphs (2006) Discrete Applied Mathematics, 154, pp. 1783-1790. , 13
  • Durán, G., Lin, M.L., Szwarcfiter, J.L., On clique-transversals and clique-independent sets (2002) Annals of Operations Research, 116, pp. 71-77
  • Erdös, P., Gallai, T., Tuza, Z., Covering the cliques of a graph with vertices (1992) Discrete Mathematics, 108, pp. 279-289
  • Gavril, F., Algorithms on circular-arc graphs (1974) Networks, 4, pp. 357-369
  • Guruswami, V., Pandu Rangan, C., Algorithmic aspects of clique transversals and clique independent sets (2000) Discrete Applied Mathematics, 100, pp. 183-202
  • Hsu, W.L., Tsai, K.H., Linear time algorithms on circular-arc graphs (1991) Information Processing Letters, 40, pp. 123-129
  • Joeris, B.C., McConnell, R.M., Spinrad, J.P., Helly circular-arc graphs (2006) SIAM Conference on Discrete Mathematics, , Victoria
  • Lee, C.M., Chang, M.S., Sheu, S.C., The clique transversal and clique independence of distance hereditary graphs (2002) Proceedings of the 19th Workshop on Combinatorial Mathematics and Computation Theory, pp. 64-69. , Taiwan
  • Lin, M., Szwarcfiter, J., Characterizations and linear time recognition of Helly circular-arc graphs (2006) Lecture Notes in Computer Science, 4112, pp. 73-82. , Proceedings of the 12th annual international conference on computing and combinatorics (COCOON'06)
  • Payan, C., Remarks on cliques and dominating sets in graphs (1979) Ars Combinatoria, 7, pp. 181-189
  • Tuza, Z., Covering all cliques of a graph (1990) Discrete Mathematics, 86, pp. 117-126

Citas:

---------- APA ----------
Durán, G., Lin, M.C., Mera, S. & Szwarcfiter, J.L. (2008) . Algorithms for finding clique-transversals of graphs. Annals of Operations Research, 157(1), 37-45.
http://dx.doi.org/10.1007/s10479-007-0189-x
---------- CHICAGO ----------
Durán, G., Lin, M.C., Mera, S., Szwarcfiter, J.L. "Algorithms for finding clique-transversals of graphs" . Annals of Operations Research 157, no. 1 (2008) : 37-45.
http://dx.doi.org/10.1007/s10479-007-0189-x
---------- MLA ----------
Durán, G., Lin, M.C., Mera, S., Szwarcfiter, J.L. "Algorithms for finding clique-transversals of graphs" . Annals of Operations Research, vol. 157, no. 1, 2008, pp. 37-45.
http://dx.doi.org/10.1007/s10479-007-0189-x
---------- VANCOUVER ----------
Durán, G., Lin, M.C., Mera, S., Szwarcfiter, J.L. Algorithms for finding clique-transversals of graphs. Ann. Oper. Res. 2008;157(1):37-45.
http://dx.doi.org/10.1007/s10479-007-0189-x