On minimum reload cost paths, tours, and flows

DOI10.1002/net.20423zbMath1219.68121OpenAlexW1998235168MaRDI QIDQ3008920

Francesco Maffioli, Giulia Galbiati, Edoardo Amaldi

Publication date: 22 June 2011

Published in: Networks (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/net.20423

zbMATH Keywords

computational complexitynetwork optimizationextended reload cost model

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Flows in graphs (05C21)

Related Items (22)

Minimization and maximization versions of the quadratic travelling salesman problem ⋮ On Minimum Reload Cost Cycle Cover ⋮ Exact algorithms and heuristics for the quadratic traveling salesman problem with an application in bioinformatics ⋮ Lower bounding procedure for the asymmetric quadratic traveling salesman problem ⋮ Reload cost trees and network design ⋮ Parameterized complexity of the MinCCA problem on graphs of bounded decomposability ⋮ The quadratic cycle cover problem: special cases and efficient bounds ⋮ Minimum <scp>color‐degree</scp> perfect b‐matchings ⋮ Parameterized complexity of finding a spanning tree with minimum reload cost diameter ⋮ The symmetric quadratic traveling salesman problem ⋮ Quadratic Combinatorial Optimization Using Separable Underestimators ⋮ On the complexity of constructing minimum changeover cost arborescences ⋮ On minimum reload cost cycle cover ⋮ An extended approach for lifting clique tree inequalities ⋮ The quadratic shortest path problem: complexity, approximability, and solution methods ⋮ The Minimum Reload s-t Path/Trail/Walk Problems ⋮ The minimum reload \(s-t\) path, trail and walk problems ⋮ Constructing minimum changeover cost arborescenses in bounded treewidth graphs ⋮ Exact and Heuristic Algorithms for Capacitated Vehicle Routing Problems with Quadratic Costs Structure ⋮ Minimum reload cost graph factors ⋮ A Polyhedral Study of the Quadratic Traveling Salesman Problem ⋮ Unnamed Item

Cites Work

• The complexity of a minimum reload cost diameter problem
• Reload cost trees and network design
• The Minimum Reload s-t Path/Trail/Walk Problems
• Reload cost problems: Minimum diameter spanning tree
• Unnamed Item

This page was built for publication: On minimum reload cost paths, tours, and flows