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

DOI10.1016/J.TCS.2011.07.012MaRDI QIDQ653316zbMATHOpenAlexFDO

Authors Sara Mattia, Flavia Bonomo, 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) Coloring of graphs and hypergraphs (05C15) Transportation, logistics and supply chain management (90B06)

Recommendations

• What are the worst cases in constrained last-in-first-out pick-up and delivery problems?
• On the Complexity of the Multiple Stack TSP, kSTSP
• Exact algorithms for the double vehicle routing problem with multiple stacks
• Approximation of the double traveling salesman problem with multiple stacks
• A branch-and-bound algorithm for the double travelling salesman problem with two stacks

Cites work

• scientific article; zbMATH DE number 1640601 (Why is no real title available?)
• scientific article; zbMATH DE number 1333600 (Why is no real title available?)
• scientific article; zbMATH DE number 512913 (Why is no real title available?)
• scientific article; zbMATH DE number 219236 (Why is no real title available?)
• scientific article; zbMATH DE number 949303 (Why is no real title available?)
• scientific article; zbMATH DE number 871903 (Why is no real title available?)
• scientific article; zbMATH DE number 6472574 (Why is no real title available?)
• scientific article; zbMATH DE number 3344609 (Why is no real title available?)
• A Characterization of Comparability Graphs and of Interval Graphs
• A note on the decomposition of graphs into isomorphic matchings
• An exact method for the double TSP with multiple stacks
• An existential problem of a weight-controlled subset and its application to school timetable construction
• Bounded vertex coloring of trees
• Bounded vertex colorings of graphs
• Chromatic optimisation: Limitations, objectives, uses, references
• Equitable Coloring
• Equitable colorings of bounded treewidth graphs
• Exact solutions to the double travelling salesman problem with multiple stacks
• Mutual exclusion scheduling
• NP-completeness of graph decomposition problems
• New neighborhood structures for the double traveling salesman problem with multiple stacks
• Restrictions of graph partition problems. I
• The complexity of comparability graph recognition and coloring
• 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
• The mutual exclusion scheduling problem for permutation and comparability graphs.
• The stable set problem and the thinness of a graph
• The χt-coloring problem
• Transitive Orientation of Graphs and Identification of Permutation Graphs

Cited in

(16)

• The bounded beam search algorithm for the block relocation problem
• On \(H\)-topological intersection graphs
• On the thinness of trees
• Thinness and its variations on some graph families and coloring graphs of bounded thinness
• A branch-and-cut algorithm for the restricted block relocation problem
• Thinness of product graphs
• What are the worst cases in constrained last-in-first-out pick-up and delivery problems?
• On the thinness and proper thinness of a graph
• Approximation of the double traveling salesman problem with multiple stacks
• Weighted and locally bounded list-colorings in split graphs, cographs, and partial \(k\)-trees
• Intersection models and forbidden pattern characterizations for 2-thin and proper 2-thin graphs
• Solving problems on generalized convex graphs via mim-width
• 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
• Polyhedral results and a branch-and-cut algorithm for the double traveling salesman problem with multiple stacks
• Precedence thinness in graphs

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q653316)