Minimum weighted clique cover on strip-composed perfect graphs | ||
| dc.conicet.organizacion | Consejo Nacional de Investigaciones Científicas y Técnicas. Oficina de Coordinación Administrativa Ciudad Universitaria. Instituto de Investigaciones Matemáticas "Luis A. Santaló". Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Instituto de Investigaciones Matemáticas "Luis A. Santaló" | |
| dc.conicet.organizacion | Universita Tor Vergata | |
| dc.conicet.organizacion | Universita Tor Vergata | |
| dc.conicet.rol | Autor | |
| dc.conicet.rol | Autor | |
| dc.conicet.rol | Autor | |
| dc.contributor.author | Bonomo, Flavia | |
| dc.contributor.author | Oriolo, Gianpaolo | |
| dc.contributor.author | Snels, Claudia | |
| dc.coverage | Internacional | |
| dc.date.evento | 2012-06-26 | |
| dc.date.eventoHasta | 2012-06-28 | |
| dc.date.issued | 2012 | es |
| dc.description.abstract | 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 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 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. | es |
| dc.description.ciudadEvento | Jerusalem | 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 Investigaciones Matemáticas "Luis A. Santaló". Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Instituto de Investigaciones Matemáticas "Luis A. Santaló"; Argentina | |
| dc.description.fil | Fil: Oriolo, Gianpaolo. Universita Tor Vergata; Italia | |
| dc.description.fil | Fil: Snels, Claudia. Universita Tor Vergata; Italia | |
| dc.description.institucionOrganizadora | International Workshop on Graph Theoretic Concepts in Computer Science | es |
| dc.description.nombreEvento | 38th International Workshop on Graph Theoretic Concepts in Computer Science | es |
| dc.description.paisEvento | Israel | es |
| dc.format | application/pdf | es |
| dc.identifier.citation | Minimum weighted clique cover on strip-composed perfect graphs; 38th International Workshop on Graph Theoretic Concepts in Computer Science; Jerusalem; Israel; 2012; 22-33 | es |
| dc.identifier.institucional | CONICET | |
| dc.identifier.isbn | 978-3-642-34611-8 | es |
| dc.identifier.issn | 0302-9743 | es |
| dc.identifier.repo | CONICET Digital | |
| dc.identifier.uri | http://hdl.handle.net/11336/279279 | |
| dc.journal.ciudad | New York | es |
| dc.journal.pagination | 22-33 | es |
| dc.journal.pais | Estados Unidos | es |
| dc.journal.volume | 7551 | es |
| dc.language.iso | eng | es |
| dc.publisher | Springer | es |
| dc.relation.alternativeid | info:eu-repo/semantics/altIdentifier/doi/http://dx.doi.org/10.1007/978-3-642-34611-8_6 | |
| dc.relation.alternativeid | info:eu-repo/semantics/altIdentifier/url/https://link.springer.com/chapter/10.1007/978-3-642-34611-8_6 | |
| dc.rights | info:eu-repo/semantics/restrictedAccess | * |
| dc.rights.uri | https://creativecommons.org/licenses/by-nc-sa/2.5/ar/ | * |
| dc.source.revista | Lecture Notes in Computer Science | es |
| dc.subject | CLAW-FREE GRAPHS | es |
| dc.subject | PERFECT GRAPHS | es |
| dc.subject | MINIMUM WEIGHTED CLIQUE COVER | es |
| dc.subject | ODD PAIRS OF CLIQUES | es |
| dc.subject | STRIP-COMPOSED GRAPHS | es |
| dc.subject.classification | Matemática Aplicada | es |
| dc.subject.classification | Matemáticas | es |
| dc.subject.classification | CIENCIAS NATURALES Y EXACTAS | 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.title | Minimum weighted clique cover on strip-composed perfect graphs | es |
| dc.type | info:eu-repo/semantics/publishedVersion | |
| dc.type | info:eu-repo/semantics/conferenceObject | |
| dc.type | info:ar-repo/semantics/documento de conferencia | |
| dc.type.publicacion | Journal | es |
| dc.type.subtype | Workshop | es |
Archivos
Bloque original
Cargando...
- Nombre:
- CONICET_Digital_Nro.debc7e35-7e6b-46a1-a235-58930c845f42_B.pdf
- Tamaño:
- 224.72 KB
- Formato:
- Adobe Portable Document Format