Artículo

Bonomo, F.; Oriolo, G.; Snels, C. "Minimum weighted clique cover on strip-composed perfect graphs" (2012) 38th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2012. 7551 LNCS:22-33
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:

The only available combinatorial algorithm for the minimum weighted clique cover (mwcc) in claw-free perfect graphs is due to Hsu and Nemhauser [10] and dates back to 1984. More recently, Chudnovsky and Seymour [3] introduced a composition operation, strip-composition, in order to define their structural results for claw-free graphs; however, this composition operation is general and applies to non-claw-free graphs as well. In this paper, we show that a mwcc of a perfect strip-composed graph, with the basic graphs belonging to a class, can be found in polynomial time, provided that the mwcc problem can be solved on in polynomial time. We also design a new, more efficient, combinatorial algorithm for the mwcc problem on strip-composed claw-free perfect graphs. © 2012 Springer-Verlag Berlin Heidelberg.

Registro:

Documento: Artículo
Título:Minimum weighted clique cover on strip-composed perfect graphs
Autor:Bonomo, F.; Oriolo, G.; Snels, C.
Ciudad:Jerusalem
Filiación:IMAS-CONICET and Departamento de Computación, FCEN, Universidad de Buenos Aires, Argentina
Dipartimento di Informatica, Sistemi e Produzione, Università di Roma Tor Vergata, Italy
Palabras clave:claw-free graphs; minimum weighted clique cover; odd pairs of cliques; perfect graphs; strip-composed graphs; Claw-free graphs; Clique cover; odd pairs of cliques; Perfect graph; strip-composed graphs; Algorithms; Computer science; Graphic methods; Polynomial approximation; Graph theory
Año:2012
Volumen:7551 LNCS
Página de inicio:22
Página de fin:33
DOI: http://dx.doi.org/10.1007/978-3-642-34611-8_6
Título revista:38th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2012
Título revista abreviado:Lect. Notes Comput. Sci.
ISSN:03029743
Registro:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03029743_v7551LNCS_n_p22_Bonomo

Referencias:

  • Burlet, M., Maffray, F., Trotignon, N., Odd pairs of cliques (2007) Proc. of A Conference in Memory of Claude Berge, pp. 85-95. , Birkhäuser
  • Chudnovskym, Seymour, P., Claw-free Graphs VII, , Quasi-line graphs. J. Combin. Theory, Ser. B (to appear
  • Chudnovsky, M., Seymour, P., The structure of claw-free graphs (2005) London Math. Soc. Lecture Note Ser., 327, pp. 153-171
  • Eisenbrand, F., Oriolo, G., Stauffer, G., Ventura, P., Circular one matrices and the stable set polytope of quasi-line graphs (2008) Combinatorica, 28 (1), pp. 45-67
  • Faenza, Y., Oriolo, G., Stauffer, G., An algorithmic decomposition of claw-free graphs leading to an O(n3)-algorithm for the weighted stable set problem (2011) Proc. 22nd SODA, pp. 630-646. , Randall, D. (ed.) San Francisco CA
  • Gabow, H., Data structures for weighted matching and nearest common ancestors with linking (1990) Proc. 1st SODA, pp. 434-443. , San Francisco CA
  • Grötschel, M., Lovász, L., Schrijver, A., (1988) Geometric Algorithms and Combinatorial Optimization, , Springer, Berlin
  • Hermelin, D., Mnich, M., Van Leeuwen, E., Woeginger, G., Domination when the stars are out (2011) ICALP 2011. LNCS, 6755, pp. 462-473. , Aceto, L., Henzinger, M., Sgall, J. (eds.) Springer, Heidelberg
  • Hsu, W., Nemhauser, G., Algorithms for minimum covering by cliques and maximum clique in claw-free perfect graphs (1981) Discrete Math., 37, pp. 181-191
  • Hsu, W., Nemhauser, G., Algorithms for maximum weight cliques, minimum weighted clique covers and cardinality colorings of claw-free perfect graphs (1984) Ann. Discrete Math., 21, pp. 317-329
  • Minty, G., On maximal independent sets of vertices in claw-free graphs (1980) J. Combin. Theory, Ser. B, 28 (3), pp. 284-304
  • Nakamura, D., Tamura, A., A revision of Minty's algorithm for finding a maximum weighted stable set of a claw-free graph (2001) J. Oper. Res. Soc. Japan, 44 (2), pp. 194-204
  • Nobili, P., Sassano, A., A reduction algorithm for the weighted stable set problem in claw-free graphs (2011) Proc. 10th CTW, pp. 223-226. , Frascati Italy
  • Oriolo, G., Pietropaoli, U., Stauffer, G., A new algorithm for the maximum weighted stable set problem in claw-free graphs (2008) IPCO 2008. LNCS, 5035, pp. 77-96. , Lodi, A., Panconesi, A., Rinaldi, G. (eds.)Springer, Heidelberg
  • Schrijver, A., Combinatorial optimization (2003) Polyhedra and Efficiency(3 Volumes Algorithms and Combinatorics, 24. , Springer Berlin
  • Trotter, L., Line perfect graphs (1977) Math. Program., 12, pp. 255-259A4 - University of Haifa; Caesarea Rothschild Inst. Interdiscip. Appl. Comput. Sci.; I-Core - Israeli Center of Excellence in Algorithms; Springer

Citas:

---------- APA ----------
Bonomo, F., Oriolo, G. & Snels, C. (2012) . Minimum weighted clique cover on strip-composed perfect graphs. 38th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2012, 7551 LNCS, 22-33.
http://dx.doi.org/10.1007/978-3-642-34611-8_6
---------- CHICAGO ----------
Bonomo, F., Oriolo, G., Snels, C. "Minimum weighted clique cover on strip-composed perfect graphs" . 38th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2012 7551 LNCS (2012) : 22-33.
http://dx.doi.org/10.1007/978-3-642-34611-8_6
---------- MLA ----------
Bonomo, F., Oriolo, G., Snels, C. "Minimum weighted clique cover on strip-composed perfect graphs" . 38th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2012, vol. 7551 LNCS, 2012, pp. 22-33.
http://dx.doi.org/10.1007/978-3-642-34611-8_6
---------- VANCOUVER ----------
Bonomo, F., Oriolo, G., Snels, C. Minimum weighted clique cover on strip-composed perfect graphs. Lect. Notes Comput. Sci. 2012;7551 LNCS:22-33.
http://dx.doi.org/10.1007/978-3-642-34611-8_6