Mostrar el registro sencillo del ítem
dc.contributor.author
Bonomo, Flavia
![Se ha confirmado la validez de este valor de autoridad por un usuario](/themes/CONICETDigital/images/authority_control/invisible.gif)
dc.contributor.author
Mattia, Sara
dc.contributor.author
Oriolo, Gianpaolo
dc.date.available
2017-04-06T20:42:55Z
dc.date.issued
2011-11
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
dc.identifier.issn
0304-3975
dc.identifier.uri
http://hdl.handle.net/11336/14909
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.
dc.format
application/pdf
dc.language.iso
eng
dc.publisher
Elsevier
![Se ha confirmado la validez de este valor de autoridad por un usuario](/themes/CONICETDigital/images/authority_control/invisible.gif)
dc.rights
info:eu-repo/semantics/openAccess
dc.rights.uri
https://creativecommons.org/licenses/by-nc-sa/2.5/ar/
dc.subject
Bounded Coloring
dc.subject
Capacitated Coloring
dc.subject
Equitable Coloring
dc.subject
Permutation Graphs
dc.subject
Scheduling Problems
dc.subject
Thinness
dc.subject.classification
Matemática Aplicada
![Se ha confirmado la validez de este valor de autoridad por un usuario](/themes/CONICETDigital/images/authority_control/invisible.gif)
dc.subject.classification
Matemáticas
![Se ha confirmado la validez de este valor de autoridad por un usuario](/themes/CONICETDigital/images/authority_control/invisible.gif)
dc.subject.classification
CIENCIAS NATURALES Y EXACTAS
![Se ha confirmado la validez de este valor de autoridad por un usuario](/themes/CONICETDigital/images/authority_control/invisible.gif)
dc.subject.classification
Ciencias de la Computación
![Se ha confirmado la validez de este valor de autoridad por un usuario](/themes/CONICETDigital/images/authority_control/invisible.gif)
dc.subject.classification
Ciencias de la Computación e Información
![Se ha confirmado la validez de este valor de autoridad por un usuario](/themes/CONICETDigital/images/authority_control/invisible.gif)
dc.subject.classification
CIENCIAS NATURALES Y EXACTAS
![Se ha confirmado la validez de este valor de autoridad por un usuario](/themes/CONICETDigital/images/authority_control/invisible.gif)
dc.title
Bounded coloring of co-comparability graphs and the pickup and delivery tour combination problem
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
2017-04-05T15:12:40Z
dc.journal.volume
412
dc.journal.number
45
dc.journal.pagination
6261-6268
dc.journal.pais
Países Bajos
![Se ha confirmado la validez de este valor de autoridad por un usuario](/themes/CONICETDigital/images/authority_control/invisible.gif)
dc.journal.ciudad
Amsterdam
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.journal.title
Theoretical Computer Science
![Se ha confirmado la validez de este valor de autoridad por un usuario](/themes/CONICETDigital/images/authority_control/invisible.gif)
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
Archivos asociados