On the complexity of constructing minimum changeover cost arborescences

DOI10.1016/J.TCS.2014.03.023MaRDI QIDQ2453161zbMATH OpenOpenAlexFDO

Authors Didem Gözüpek, Mordechai Shalom, Ariella Voloshin, 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

approximation algorithmsnetwork designnetwork optimizationchangeover costreload cost

Mathematics Subject Classification ID

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

Recommendations

• Constructing minimum changeover cost arborescenses in bounded treewidth graphs
• On minimum changeover cost arborescences
• Complexity of edge coloring with minimum reload/changeover costs
• On minimum reload cost paths, tours, and flows

Cites work

• scientific article; zbMATH DE number 3688740 (Why is no real title available?)
• scientific article; zbMATH DE number 3573250 (Why is no real title available?)
• scientific article; zbMATH DE number 1330032 (Why is no real title available?)
• scientific article; zbMATH DE number 1330033 (Why is no real title available?)
• scientific article; zbMATH DE number 1559541 (Why is no real title available?)
• scientific article; zbMATH DE number 1559563 (Why is no real title available?)
• A Greedy Heuristic for the Set-Covering Problem
• Graph Classes: A Survey
• Graph theory
• NeXt generation/dynamic spectrum access/cognitive radio wireless networks: a survey
• On minimum changeover cost arborescences
• On minimum reload cost cycle cover
• On minimum reload cost paths, tours, and flows
• Reload cost problems: Minimum diameter spanning tree
• Reload cost trees and network design
• The complexity of a minimum reload cost diameter problem
• The minimum reload \(s-t\) path, trail and walk problems

Cited in

(7)

• Reload cost trees and network design
• Constructing minimum changeover cost arborescenses in bounded treewidth graphs
• On minimum changeover cost arborescences
• Parameterized complexity of finding a spanning tree with minimum reload cost diameter
• Parameterized complexity of finding a spanning tree with minimum reload cost diameter
• Complexity of edge coloring with minimum reload/changeover costs
• Reload cost problems: Minimum diameter spanning tree

This page was built for publication: On the complexity of constructing minimum changeover cost arborescences

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