Exploring the complexity boundary between coloring and list-coloring | ||
| 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 | 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 | Universidad Nacional de General Sarmiento. Instituto de Ciencias | |
| dc.contributor.author | Bonomo, Flavia | |
| dc.contributor.author | Duran, Guillermo Alfredo | |
| dc.contributor.author | Marenco, Javier Leonardo | |
| dc.date.issued | 2008-07 | |
| dc.description.abstract | Many classes of graphs where the vertex coloring problem is polynomially solvable are known, the most prominent being the class of perfect graphs. However, the list-coloring problem is NP-complete for many subclasses of perfect graphs. In this work we explore the complexity boundary between vertex coloring and list-coloring on such subclasses of perfect graphs where the former admits polynomial-time algorithms but the latter is NP-complete. Our goal is to analyze the computational complexity of coloring problems lying “between” (from a computational complexity viewpoint) these two problems: precoloring extension, μ-coloring, and (γ,μ)-coloring. | 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: Duran, Guillermo Alfredo. 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: Marenco, Javier Leonardo. Universidad Nacional de General Sarmiento. Instituto de Ciencias; Argentina | |
| dc.format | application/pdf | es |
| dc.identifier.citation | Bonomo, Flavia; Duran, Guillermo Alfredo; Marenco, Javier Leonardo; Exploring the complexity boundary between coloring and list-coloring; Springer; Annals Of Operations Research; 169; 1; 7-2008; 3-16 | es |
| dc.identifier.institucional | CONICET | |
| dc.identifier.issn | 0254-5330 | es |
| dc.identifier.repo | CONICET Digital | |
| dc.identifier.uri | http://hdl.handle.net/11336/242433 | |
| dc.journal.ciudad | Berlín | es |
| dc.journal.number | 1 | es |
| dc.journal.pagination | 3-16 | es |
| dc.journal.pais | Alemania | es |
| dc.journal.title | Annals Of Operations Research | es |
| dc.journal.volume | 169 | es |
| dc.language.iso | eng | es |
| dc.publisher | Springer | es |
| dc.relation.alternativeid | info:eu-repo/semantics/altIdentifier/url/https://link.springer.com/article/10.1007/s10479-008-0391-5 | |
| dc.relation.alternativeid | info:eu-repo/semantics/altIdentifier/doi/http://dx.doi.org/10.1007/s10479-008-0391-5 | |
| dc.rights | info:eu-repo/semantics/restrictedAccess | * |
| dc.rights.uri | https://creativecommons.org/licenses/by-nc-sa/2.5/ar/ | * |
| dc.subject | COLORING | es |
| dc.subject | COMPUTATIONAL COMPLEXITY | es |
| dc.subject | LIST-COLORING | 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 | Exploring the complexity boundary between coloring and list-coloring | 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.bedc793b-23df-4b67-bfa0-c44119a7bfdb_E.pdf
- Tamaño:
- 372.65 KB
- Formato:
- Adobe Portable Document Format