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

DOI10.1016/j.tcs.2011.07.012zbMath1230.90030OpenAlexW1980537145MaRDI 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

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Transportation, logistics and supply chain management (90B06) Coloring of graphs and hypergraphs (05C15)

Related Items (15)

Thinness of product graphs ⋮ The bounded beam search algorithm for the block relocation problem ⋮ The traveling purchaser problem, with multiple stacks and deliveries: a branch-and-cut approach ⋮ What are the worst cases in constrained last-in-first-out pick-up and delivery problems? ⋮ Exact algorithms for the double vehicle routing problem with multiple stacks ⋮ On the thinness and proper thinness of a graph ⋮ Intersection models and forbidden pattern characterizations for 2-thin and proper 2-thin graphs ⋮ Weighted and locally bounded list-colorings in split graphs, cographs, and partial \(k\)-trees ⋮ On the thinness of trees ⋮ Solving problems on generalized convex graphs via mim-width ⋮ Polyhedral results and a branch-and-cut algorithm for the double traveling salesman problem with multiple stacks ⋮ A branch-and-cut algorithm for the restricted block relocation problem ⋮ Approximation of the double traveling salesman problem with multiple stacks ⋮ On \(H\)-topological intersection graphs ⋮ Precedence thinness in graphs

Cites Work

• 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
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Bounded coloring of co-comparability graphs and the pickup and delivery tour combination problem