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
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
