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

Flavia Bonomo (), Sara Mattia () and Gianpaolo Oriolo ()
Additional contact information
Flavia Bonomo: Universidad de Buenos Aires, Buenos Aires, Argentina
Sara Mattia: Dipartimento di Informatica e Sistemistica "Antonio Ruberti" Sapienza, Universita' di Roma
Gianpaolo Oriolo: Dipartimento di Ingegneria dell'Impresa Universita' di Roma "Tor Vergata", Roma, Italy

No 2010-06, DIS Technical Reports from Department of Computer, Control and Management Engineering, Universita' degli Studi di Roma "La Sapienza"

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. In 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 [25].

Keywords: bounded coloring; capacitated coloring; equitable coloring; permutation graphs; scheduling problems; thinness (search for similar items in EconPapers)
Date: 2010-07
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.dis.uniroma1.it/~bibdis/RePEc/aeg/wpaper/2010-06.pdf First version, 2010 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:aeg:wpaper:2010-6

Access Statistics for this paper

More papers in DIS Technical Reports from Department of Computer, Control and Management Engineering, Universita' degli Studi di Roma "La Sapienza" Contact information at EDIRC.
Bibliographic data for series maintained by Antonietta Angelica Zucconi ( this e-mail address is bad, please contact ).