IMAS 23417
INSTITUTO DE INVESTIGACIONES MATEMATICAS "LUIS A. SANTALO"
Unidad Ejecutora - UE
artículos
Título:
Minimum Weighted Clique Cover on Strip-Composed Perfect Graphs
Autor/es:
BONOMO, FLAVIA; ORIOLO, GIANPAOLO; SNELS, CLAUDIA
Revista:
LECTURE NOTES IN COMPUTER SCIENCE
Editorial:
Springer-Verlag
Referencias:
Año: 2012 vol. 7551 p. 22 - 33
ISSN:
0302-9743
Resumen:
The only available combinatorial algorithm for the minimum weighted clique cover (MWCC) in claw-free perfect graphs is due to Hsu and Nemhauser and dates back to 1984. More recently, Chudnovsky and Seymour introduced a composition operation, strip-composition, in order todefine 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 perfectstrip-composed graph, with the basic graphs belonging to a class G, can be found in polynomial time, provided that the MWCC problem can be solved on G in polynomial time. We also design a new, more efficient, combinatorial algorithm for the MWCC problem on strip-composed claw-free perfect graphs.
