Navegar

Colección

Datos Estadísticas

Artículo

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:

Given a graph G=(V,E) a clique is a maximal subset of pairwise adjacent vertices of V of size at least 2. A clique transversal is a subset of vertices that intersects the vertex set of each clique of G. Finding a minimum-cardinality clique transversal is NP-hard for the following classes: planar, line and bounded degree graphs. For line graphs we present a 3-approximation for the unweighted case and a 4-approximation for the weighted case with nonnegative weights; a ⌈(Δ(G)+1)/2 ⌉(-approximation for bounded degree graphs and a 3-approximation for planar graphs. © 2015 Elsevier B.V.

Registro:

Documento: Artículo
Título:Approximation algorithms for clique transversals on some graph classes
Autor:Lin, M.C.; Vasiliev, S.
Filiación:CONICET and Instituto de Cálculo, FCEyN, Universidad de Buenos Aires, Argentina
Palabras clave:Approximation algorithms; Clique transversal; Graph classes; NP-hard; Algorithms; Distributed computer systems; Graph theory; Graphic methods; Adjacent vertices; Bounded degree graphs; Cardinalities; Clique transversal; Graph class; Non negatives; NP-hard; Planar graph; Approximation algorithms
Año:2015
Volumen:115
Número:9
Página de inicio:667
Página de fin:670
DOI: http://dx.doi.org/10.1016/j.ipl.2015.04.003
Título revista:Information Processing Letters
Título revista abreviado:Inf. Process. Lett.
ISSN:00200190
CODEN:IFPLA
Registro:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_00200190_v115_n9_p667_Lin

Referencias:

  • Tuza, Z., Covering all cliques of a graph (1990) Discrete Math., 86 (13), pp. 117-126
  • Erdos, P., Gallai, T., Tuza, Z., Covering the cliques of a graph with vertices (1992) Discrete Math., 108 (13), pp. 279-289
  • Chang, G., Farber, M., Tuza, Z., Algorithmic aspects of neighborhood numbers (1993) SIAM J. Discrete Math., 6 (1), pp. 24-29
  • Lee, C.-M., Chang, M.-S., Distance-hereditary graphs are clique-perfect (2006) Discrete Appl. Math., 154 (3), pp. 525-536
  • Balachandran, V., Nagavamsi, P., Rangan, C., Clique transversal and clique independence on comparability graphs (1996) Inf. Process. Lett., 58 (4), pp. 181-184
  • Guruswami, V., Rangan, C.P., Algorithmic aspects of clique-transversal and clique-independent sets (2000) Discrete Appl. Math., 100 (3), pp. 183-202
  • Durán, G., Lin, M.C., Szwarcfiter, J.L., On clique-transversals and clique-independent sets (2002) Ann. Oper. Res., 116 (14), pp. 71-77
  • Durán, G., Lin, M.C., Mera, S., Szwarcfiter, J.L., Algorithms for finding clique-transversals of graphs (2008) Ann. Oper. Res., 157 (1), pp. 37-45
  • Liang, Z., Shan, E., Approximation algorithms for clique-transversal sets and clique-independent sets in cubic graphs (2011) Inf. Process. Lett., 111 (2324), pp. 1104-1107
  • Bertossi, A.A., Dominating sets for split and bipartite graphs (1984) Inf. Process. Lett., 19 (1), pp. 37-40
  • Roussopoulos, N.D., A max { m, n } algorithm for determining the graph H from its line graph G (1973) Inf. Process. Lett., 2 (4), pp. 108-112
  • Chiba, N., Nishizeki, T., Arboricity and subgraph listing algorithms (1985) SIAM J. Comput., 14 (1), pp. 210-223
  • Micali, S., Vazirani, V.V., An O (| v | | e |) algorithm for finding maximum matching in general graphs (1980) FOCS, pp. 17-27. , IEEE Computer Society
  • Schrijver, A., (2003) Combinatorial Optimization - Polyhedra and Efficiency, , Springer
  • Hochbaum, D.S., Approximation algorithms for the set covering and vertex cover problems (1982) SIAM J. Comput., 11 (3), pp. 555-556
  • Kuratowski, C., Sur le problme des courbes gauches en topologie (1930) Fundam. Math., 15 (1), pp. 271-283

Citas:

---------- APA ----------
Lin, M.C. & Vasiliev, S. (2015) . Approximation algorithms for clique transversals on some graph classes. Information Processing Letters, 115(9), 667-670.
http://dx.doi.org/10.1016/j.ipl.2015.04.003
---------- CHICAGO ----------
Lin, M.C., Vasiliev, S. "Approximation algorithms for clique transversals on some graph classes" . Information Processing Letters 115, no. 9 (2015) : 667-670.
http://dx.doi.org/10.1016/j.ipl.2015.04.003
---------- MLA ----------
Lin, M.C., Vasiliev, S. "Approximation algorithms for clique transversals on some graph classes" . Information Processing Letters, vol. 115, no. 9, 2015, pp. 667-670.
http://dx.doi.org/10.1016/j.ipl.2015.04.003
---------- VANCOUVER ----------
Lin, M.C., Vasiliev, S. Approximation algorithms for clique transversals on some graph classes. Inf. Process. Lett. 2015;115(9):667-670.
http://dx.doi.org/10.1016/j.ipl.2015.04.003