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