The complexity of a minimum reload cost diameter problem

DOI10.1016/j.dam.2008.02.013zbMath1168.68035OpenAlexW1980496634MaRDI QIDQ1003738

Giulia Galbiati

Publication date: 4 March 2009

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

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

zbMATH Keywords

combinatorial optimizationapproximation algorithmreload cost modelminimum diameter spanning tree

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

Related Items

On Minimum Reload Cost Cycle Cover ⋮ 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 ⋮ Combinatorial optimization with one quadratic term: spanning trees and forests ⋮ Parameterized complexity of finding a spanning tree with minimum reload cost diameter ⋮ On the complexity of constructing minimum changeover cost arborescences ⋮ On minimum reload cost cycle cover ⋮ On minimum reload cost paths, tours, and flows ⋮ 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 ⋮ Minimum reload cost graph factors ⋮ Unnamed Item ⋮ On Solving the Quadratic Shortest Path Problem

Cites Work

• Unnamed Item
• Reload cost trees and network design
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• Reload cost problems: Minimum diameter spanning tree