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

DOI10.1016/j.tcs.2011.07.012zbMath1230.90030MaRDI QIDQ653316

Sara Mattia, Flavia Bonomo-Braberman, Gianpaolo Oriolo

Publication date: 9 January 2012

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2011.07.012

Mathematics Subject Classification ID

90C35: Programming involving graphs or networks

68Q25: Analysis of algorithms and problem complexity

90B06: Transportation, logistics and supply chain management

05C15: Coloring of graphs and hypergraphs

Related Items

The traveling purchaser problem, with multiple stacks and deliveries: a branch-and-cut approach, Exact algorithms for the double vehicle routing problem with multiple stacks, The bounded beam search algorithm for the block relocation problem, What are the worst cases in constrained last-in-first-out pick-up and delivery problems?, Polyhedral results and a branch-and-cut algorithm for the double traveling salesman problem with multiple stacks, On the thinness and proper thinness of a graph, Weighted and locally bounded list-colorings in split graphs, cographs, and partial \(k\)-trees

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Restrictions of graph partition problems. I
• Bounded vertex colorings of graphs
• A note on the decomposition of graphs into isomorphic matchings
• Equitable colorings of bounded treewidth graphs
• New neighborhood structures for the double traveling salesman problem with multiple stacks
• The double traveling salesman problem with multiple stacks: A variable neighborhood search approach
• The double travelling salesman problem with multiple stacks - formulation and heuristic solution approaches
• An existential problem of a weight-controlled subset and its application to school timetable construction
• Chromatic optimisation: Limitations, objectives, uses, references
• NP-completeness of graph decomposition problems
• The complexity of comparability graph recognition and coloring
• Mutual exclusion scheduling
• The mutual exclusion scheduling problem for permutation and comparability graphs.
• The stable set problem and the thinness of a graph
• An exact method for the double TSP with multiple stacks
• Exact solutions to the double travelling salesman problem with multiple stacks
• Equitable Coloring
• The χt-coloring problem
• Transitive Orientation of Graphs and Identification of Permutation Graphs
• A Characterization of Comparability Graphs and of Interval Graphs
• Bounded vertex coloring of trees