Minimum weighted clique cover on claw-free perfect graphs | ||
| dc.conicet.organizacion | 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 | |
| dc.conicet.organizacion | Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Departamento de Computación | |
| dc.conicet.organizacion | Universita Tor Vergata | |
| dc.conicet.organizacion | Universita Tor Vergata | |
| dc.contributor.author | Bonomo, Flavia | |
| dc.contributor.author | Oriolo, Gianpaolo | |
| dc.contributor.author | Snels, Claudia | |
| dc.date.issued | 2021-01 | |
| 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. | es |
| 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.format | application/pdf | es |
| 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 | es |
| dc.identifier.institucional | CONICET | |
| dc.identifier.issn | 0364-9024 | es |
| dc.identifier.repo | CONICET Digital | |
| dc.identifier.uri | http://hdl.handle.net/11336/173296 | |
| dc.journal.ciudad | New York | es |
| dc.journal.pagination | 231-268 | es |
| dc.journal.pais | Estados Unidos | es |
| dc.journal.title | Journal of Graph Theory | es |
| dc.journal.volume | 96 | es |
| dc.language.iso | eng | es |
| dc.publisher | John Wiley & Sons Inc. | es |
| 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 | |
| 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 | es |
| dc.subject | line graphs | es |
| dc.subject | minimum weighted clique cover | es |
| dc.subject | perfect graphs | es |
| dc.subject | strip-composed graphs | es |
| dc.subject.classification | Ciencias de la Computación | es |
| dc.subject.classification | Ciencias de la Computación e Información | es |
| dc.subject.classification | CIENCIAS NATURALES Y EXACTAS | es |
| dc.subject.classification | Matemática Aplicada | es |
| dc.subject.classification | Matemáticas | es |
| dc.subject.classification | CIENCIAS NATURALES Y EXACTAS | es |
| dc.title | Minimum weighted clique cover on claw-free perfect graphs | es |
| dc.type | info:eu-repo/semantics/article | |
| dc.type | info:ar-repo/semantics/artículo | |
| dc.type | info:eu-repo/semantics/publishedVersion | |
Archivos
Bloque original
Cargando...
- Nombre:
- CONICET_Digital_Nro.bf8cac09-af8f-4fd7-83ea-7314281e1db7_B.pdf
- Tamaño:
- 1.41 MB
- Formato:
- Adobe Portable Document Format