On the complexity of constructing minimum changeover cost arborescences

DOI10.1016/j.tcs.2014.03.023zbMath1360.68479MaRDI QIDQ2453161

Ariella Voloshin, Didem Gözüpek, Mordechai Shalom, Shmuel Zaks

Publication date: 6 June 2014

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2014.03.023

zbMATH Keywords

network design; approximation algorithms; network optimization; changeover cost; reload cost

Mathematics Subject Classification ID

90C35: Programming involving graphs or networks

68R10: Graph theory (including graph drawing) in computer science

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

05C85: Graph algorithms (graph-theoretic aspects)

68W25: Approximation algorithms

Related Items

Unnamed Item, Constructing minimum changeover cost arborescenses in bounded treewidth graphs, Minimum reload cost graph factors, Parameterized complexity of finding a spanning tree with minimum reload cost diameter, Parameterized complexity of the MinCCA problem on graphs of bounded decomposability

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On minimum reload cost cycle cover
• NeXt generation/dynamic spectrum access/cognitive radio wireless networks: a survey
• The minimum reload \(s-t\) path, trail and walk problems
• The complexity of a minimum reload cost diameter problem
• Reload cost trees and network design
• On Minimum Changeover Cost Arborescences
• On minimum reload cost paths, tours, and flows
• A Greedy Heuristic for the Set-Covering Problem
• Graph Classes: A Survey
• Reload cost problems: Minimum diameter spanning tree