Mostrar el registro sencillo del ítem
dc.contributor.author
Bonomo, Flavia
dc.contributor.author
Oriolo, Gianpaolo
dc.contributor.author
Snels, Claudia
dc.date.available
2022-10-14T16:58:43Z
dc.date.issued
2021-01
dc.identifier.citation
Bonomo, Flavia; Oriolo, Gianpaolo; Snels, Claudia; Minimum weighted clique cover on claw-free perfect graphs; John Wiley & Sons Inc.; Journal of Graph Theory; 96; 1-2021; 231-268
dc.identifier.issn
0364-9024
dc.identifier.uri
http://hdl.handle.net/11336/173296
dc.description.abstract
The first combinatorial algorithm for the minimum weighted clique cover (MWCC) in a claw-free perfect graph $G$ due to Hsu and Nemhauser dates back to 1984. It is essentially a ``dual´´ algorithm as it relies on any algorithm for the maximum weighted stable set (MWSS) problem in claw-free graphs and, taking into account the best known complexity for the latter problem, its complexity is $O(|V(G)|^{5})$. More recently, Chudnovsky and Seymour 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 ${cal G}$, can be found in polynomial time, provided that the mwcc problem can be solved on ${cal G}$ in polynomial time. For the case of claw-free perfect strip-composed graphs, the algorithm can betailored so that it never requires the computation of a MWSS on the strips and can be implemented as to run in $O(|V(G)|^{3})$ time. Finally, building upon several results from the literature, we show how to deal with non-strip-composed claw-free perfect graphs, and therefore compute a MWCC in a general claw-free perfect graph in $O(|V(G)|^{3})$ time.
dc.format
application/pdf
dc.language.iso
eng
dc.publisher
John Wiley & Sons Inc.
dc.rights
info:eu-repo/semantics/restrictedAccess
dc.rights.uri
https://creativecommons.org/licenses/by-nc-sa/2.5/ar/
dc.subject
Claw-free graphs
dc.subject
line graphs
dc.subject
minimum weighted clique cover
dc.subject
perfect graphs
dc.subject
strip-composed graphs
dc.subject.classification
Ciencias de la Computación
dc.subject.classification
Ciencias de la Computación e Información
dc.subject.classification
CIENCIAS NATURALES Y EXACTAS
dc.subject.classification
Matemática Aplicada
dc.subject.classification
Matemáticas
dc.subject.classification
CIENCIAS NATURALES Y EXACTAS
dc.title
Minimum weighted clique cover on claw-free perfect graphs
dc.type
info:eu-repo/semantics/article
dc.type
info:ar-repo/semantics/artículo
dc.type
info:eu-repo/semantics/publishedVersion
dc.date.updated
2022-09-22T16:16:25Z
dc.journal.volume
96
dc.journal.pagination
231-268
dc.journal.pais
Estados Unidos
dc.journal.ciudad
New York
dc.description.fil
Fil: Bonomo, Flavia. Consejo Nacional de Investigaciones Científicas y Técnicas. Oficina de Coordinación Administrativa Ciudad Universitaria. Instituto de Investigación en Ciencias de la Computación. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Instituto de Investigación en Ciencias de la Computación; Argentina. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Departamento de Computación; Argentina
dc.description.fil
Fil: Oriolo, Gianpaolo. Universita Tor Vergata; Italia
dc.description.fil
Fil: Snels, Claudia. Universita Tor Vergata; Italia
dc.journal.title
Journal of Graph Theory
dc.relation.alternativeid
info:eu-repo/semantics/altIdentifier/doi/http://dx.doi.org/10.1002/jgt.22611
dc.relation.alternativeid
info:eu-repo/semantics/altIdentifier/url/https://onlinelibrary.wiley.com/doi/10.1002/jgt.22611
Archivos asociados