Bounded coloring of co-comparability graphs and the pickup and delivery tour combination problem

Mostrar todas las versiones(3)

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...

Descripción completa

Guardado en:
Detalles Bibliográficos
Autores principales: Bonomo, F., Mattia, S., Oriolo, G.
Formato: Artículo publishedVersion
Lenguaje:Inglés
Publicado: 2011
Materias:
Bounded coloring
Capacitated coloring
Equitable coloring
Permutation graphs
Scheduling problems
Thinness
Coloring
Graphic methods
Pickups
Polynomial approximation
Vehicle routing
Permutation graph
Scheduling problem
Traveling salesman problem
Acceso en línea:http://hdl.handle.net/20.500.12110/paper_03043975_v412_n45_p6261_Bonomo
Aporte de:
Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires
id paperaa:paper_03043975_v412_n45_p6261_Bonomo
record_format dspace
spelling paperaa:paper_03043975_v412_n45_p6261_Bonomo2023-06-12T16:47:28Z Bounded coloring of co-comparability graphs and the pickup and delivery tour combination problem Theor Comput Sci 2011;412(45):6261-6268 Bonomo, F. Mattia, S. Oriolo, G. 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 info:eu-repo/semantics/article info:ar-repo/semantics/artículo info:eu-repo/semantics/publishedVersion application/pdf eng info:eu-repo/semantics/openAccess http://creativecommons.org/licenses/by/2.5/ar 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)
language Inglés
orig_language_str_mv eng
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, F.
Mattia, S.
Oriolo, G.
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.
format Artículo
Artículo
publishedVersion
author Bonomo, F.
Mattia, S.
Oriolo, G.
author_facet Bonomo, F.
Mattia, S.
Oriolo, G.
author_sort Bonomo, F.
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 http://hdl.handle.net/20.500.12110/paper_03043975_v412_n45_p6261_Bonomo
work_keys_str_mv AT bonomof boundedcoloringofcocomparabilitygraphsandthepickupanddeliverytourcombinationproblem
AT mattias boundedcoloringofcocomparabilitygraphsandthepickupanddeliverytourcombinationproblem
AT oriolog boundedcoloringofcocomparabilitygraphsandthepickupanddeliverytourcombinationproblem
_version_ 1769810117808619520

Ejemplares similares