Bounded coloring of co-comparability graphs and the pickup and delivery tour combination problem
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 exi...
Guardado en:
Autor principal: | |
---|---|
Publicado: |
2011
|
Materias: | |
Acceso en línea: | https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03043975_v412_n45_p6261_Bonomo http://hdl.handle.net/20.500.12110/paper_03043975_v412_n45_p6261_Bonomo |
Aporte de: |
id |
paper:paper_03043975_v412_n45_p6261_Bonomo |
---|---|
record_format |
dspace |
spelling |
paper:paper_03043975_v412_n45_p6261_Bonomo2023-06-08T15:29:38Z Bounded coloring of co-comparability graphs and the pickup and delivery tour combination problem Bonomo, Flavia Bounded coloring Capacitated coloring Equitable coloring Permutation graphs Scheduling problems Thinness Coloring Graphic methods Pickups Polynomial approximation Vehicle routing Bounded coloring Equitable coloring Permutation graph Scheduling problem Thinness Traveling salesman problem 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. In the paper, weshow that the PDTC problem canbesolved in polynomial time when the number of stacks s is fixed but the size of each stack is not. We build upon the equivalence between the PDTC problem and the bounded coloring(BC) problemonpermutation 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. © 2011 Elsevier B.V. All rights reserved. Fil:Bonomo, F. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. 2011 https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03043975_v412_n45_p6261_Bonomo http://hdl.handle.net/20.500.12110/paper_03043975_v412_n45_p6261_Bonomo |
institution |
Universidad de Buenos Aires |
institution_str |
I-28 |
repository_str |
R-134 |
collection |
Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) |
topic |
Bounded coloring Capacitated coloring Equitable coloring Permutation graphs Scheduling problems Thinness Coloring Graphic methods Pickups Polynomial approximation Vehicle routing Bounded coloring Equitable coloring Permutation graph Scheduling problem Thinness Traveling salesman problem |
spellingShingle |
Bounded coloring Capacitated coloring Equitable coloring Permutation graphs Scheduling problems Thinness Coloring Graphic methods Pickups Polynomial approximation Vehicle routing Bounded coloring Equitable coloring Permutation graph Scheduling problem Thinness Traveling salesman problem Bonomo, Flavia Bounded coloring of co-comparability graphs and the pickup and delivery tour combination problem |
topic_facet |
Bounded coloring Capacitated coloring Equitable coloring Permutation graphs Scheduling problems Thinness Coloring Graphic methods Pickups Polynomial approximation Vehicle routing Bounded coloring Equitable coloring Permutation graph Scheduling problem Thinness Traveling salesman problem |
description |
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. In the paper, weshow that the PDTC problem canbesolved in polynomial time when the number of stacks s is fixed but the size of each stack is not. We build upon the equivalence between the PDTC problem and the bounded coloring(BC) problemonpermutation 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. © 2011 Elsevier B.V. All rights reserved. |
author |
Bonomo, Flavia |
author_facet |
Bonomo, Flavia |
author_sort |
Bonomo, Flavia |
title |
Bounded coloring of co-comparability graphs and the pickup and delivery tour combination problem |
title_short |
Bounded coloring of co-comparability graphs and the pickup and delivery tour combination problem |
title_full |
Bounded coloring of co-comparability graphs and the pickup and delivery tour combination problem |
title_fullStr |
Bounded coloring of co-comparability graphs and the pickup and delivery tour combination problem |
title_full_unstemmed |
Bounded coloring of co-comparability graphs and the pickup and delivery tour combination problem |
title_sort |
bounded coloring of co-comparability graphs and the pickup and delivery tour combination problem |
publishDate |
2011 |
url |
https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03043975_v412_n45_p6261_Bonomo http://hdl.handle.net/20.500.12110/paper_03043975_v412_n45_p6261_Bonomo |
work_keys_str_mv |
AT bonomoflavia boundedcoloringofcocomparabilitygraphsandthepickupanddeliverytourcombinationproblem |
_version_ |
1768544039301283840 |