The minimum reload s-t path, trail and walk problems

DOI10.1016/J.DAM.2010.03.009MaRDI QIDQ987690zbMATH OpenOpenAlexFDO

Authors Laurent Gourvès, Adria Lyra, Jérôme Monnot, Carlos Martinhon

Publication date 13 August 2010

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2010.03.009

zbMATH Keywords

TSPinapproximabilityNP-hardnessedge-colored graphspaths, trails and walksreload optimization

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Paths and cycles (05C38)

Recommendations

• The Minimum Reload s-t Path/Trail/Walk Problems
• On minimum reload cost paths, tours, and flows
• Minimum-link paths revisited
• On the complexity of minimum-link path problems
• scientific article
• Min-sum 2-paths problems
• Min-sum 2-paths problems
• On the Complexity and Approximation of the Min-Sum and Min-Max Disjoint Paths Problems
• On finding Min-Min disjoint paths
• MIN-MAX quickest path problems

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 795216 (Why is no real title available?)
• On minimum reload cost paths, tours, and flows
• Paths and trails in edge-colored graphs
• Reload cost problems: Minimum diameter spanning tree
• Reload cost trees and network design
• The complexity of a minimum reload cost diameter problem

Cited in

(18)

• On minimum reload cost cycle cover
• Complexity of edge coloring with minimum reload/changeover costs
• Vertex alternating-pancyclism in 2-edge-colored generalized sums of graphs
• The Minimum Reload s-t Path/Trail/Walk Problems
• A new sufficient condition for the existence of alternating Hamiltonian cycles in 2-edge-colored multigraphs
• On minimum reload cost paths, tours, and flows
• Quadratic Combinatorial Optimization Using Separable Underestimators
• The quadratic cycle cover problem: special cases and efficient bounds
• Exact and heuristic algorithms for capacitated vehicle routing problems with quadratic costs structure
• Alternating-pancyclism in 2-edge-colored graphs
• Parameterized complexity of finding a spanning tree with minimum reload cost diameter
• Minimum reload cost cycle cover in complete graphs
• Parameterized complexity of finding a spanning tree with minimum reload cost diameter
• On the complexity of constructing minimum changeover cost arborescences
• The symmetric quadratic traveling salesman problem
• Paths and trails in edge-colored weighted graphs
• Constructing minimum changeover cost arborescenses in bounded treewidth graphs
• The quadratic shortest path problem: complexity, approximability, and solution methods

This page was built for publication: The minimum reload \(s-t\) path, trail and walk problems

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