On the complexity of constructing minimum changeover cost arborescences

DOI10.1016/j.tcs.2014.03.023zbMath1360.68479OpenAlexW2012371405MaRDI 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 designapproximation algorithmsnetwork optimizationchangeover costreload cost

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items

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

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