Bounded coloring of co-comparability graphs and the pickup and delivery tour combination problem | ||
| dc.conicet.organizacion | Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Departamento de Computación | |
| 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ó" | |
| dc.conicet.organizacion | Technische Universität Dortmund | |
| dc.conicet.organizacion | Universita Tor Vergata | |
| dc.contributor.author | Bonomo, Flavia | |
| dc.contributor.author | Mattia, Sara | |
| dc.contributor.author | Oriolo, Gianpaolo | |
| dc.date.issued | 2011-11 | |
| dc.description.abstract | The Double Traveling Salesman Problem with Multiple Stacks is a vehicle routing problem in which pickups and deliveries must be performed in two independent networks. The items are stored in stacks and repacking is not allowed. Given a pickup and a delivery tour, the problem of checking if there exists a valid distribution of items into s stacks of size h that is consistent with the given tours, is known as Pickup and Delivery Tour Combination (PDTC) problem. n the paper, we show that the PDTC problem can be solved in polynomial time when the number s of stacks is fixed but the size of each stack is not. We build upon the equivalence between the PDTC problem and the bounded coloring (BC) problem on permutation graphs: for the latter problem, s is the number of colors and h is the number of vertices that can get a same color. We show that the BC problem can be solved in polynomial time when s is a fixed constant on co-comparability graphs, a superclass of permutation graphs. To the contrary, the BC problem is known to be hard on permutation graphs when h≥ 6 is a fixed constant, but s is unbounded. | es |
| dc.description.fil | Fil: Bonomo, Flavia. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Departamento de Computación; Argentina. Consejo Nacional de Investigaciones Científicas y Técnicas. Oficina de Coordinación Administrativa Ciudad Universitaria. Instituto de Investigaciones Matemáticas "Luis A. Santaló"; Argentina | |
| dc.description.fil | Fil: Mattia, Sara. Technische Universität Dortmund; Alemania | |
| dc.description.fil | Fil: Oriolo, Gianpaolo. Universita Tor Vergata; Italia | |
| dc.format | application/pdf | es |
| dc.identifier.citation | Bonomo, Flavia; Mattia, Sara; Oriolo, Gianpaolo; Bounded coloring of co-comparability graphs and the pickup and delivery tour combination problem; Elsevier; Theoretical Computer Science; 412; 45; 11-2011; 6261-6268 | es |
| dc.identifier.issn | 0304-3975 | es |
| dc.identifier.uri | http://hdl.handle.net/11336/14909 | |
| dc.journal.ciudad | Amsterdam | es |
| dc.journal.number | 45 | es |
| dc.journal.pagination | 6261-6268 | es |
| dc.journal.pais | Países Bajos | es |
| dc.journal.title | Theoretical Computer Science | es |
| dc.journal.volume | 412 | es |
| dc.language.iso | eng | es |
| dc.publisher | Elsevier | es |
| dc.relation.alternativeid | info:eu-repo/semantics/altIdentifier/doi/http://dx.doi.org/10.1016/j.tcs.2011.07.012 | |
| dc.relation.alternativeid | info:eu-repo/semantics/altIdentifier/url/http://www.sciencedirect.com/science/article/pii/S0304397511006220 | |
| dc.rights | info:eu-repo/semantics/openAccess | * |
| dc.rights.uri | https://creativecommons.org/licenses/by-nc-sa/2.5/ar/ | * |
| dc.subject | Bounded Coloring | es |
| dc.subject | Capacitated Coloring | es |
| dc.subject | Equitable Coloring | es |
| dc.subject | Permutation Graphs | es |
| dc.subject | Scheduling Problems | es |
| dc.subject | Thinness | 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 | Bounded coloring of co-comparability graphs and the pickup and delivery tour combination problem | 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.18296.pdf
- Tamaño:
- 271.84 KB
- Formato:
- Adobe Portable Document Format
- Descripción: