On the complexity of the regenerator location problem treewidth and other parameters

DOI10.1016/j.dam.2015.01.036zbMath1326.05148OpenAlexW2004418970MaRDI QIDQ896670

Mordechai Shalom, Shmuel Zaks, Itamar Hartstein

Publication date: 10 December 2015

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

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

zbMATH Keywords

algorithmsoptical networkshardness of approximationparameterized complexityswitching cost

Mathematics Subject Classification ID

Small world graphs, complex networks (graph-theoretic aspects) (05C82) Network design and communication in computer systems (68M10) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the complexity of the regenerator cost problem in general networks with traffic grooming
• Optimizing regenerator cost in traffic grooming
• Minimizing total busy time in parallel scheduling with application to optical networks
• Linear time algorithms for NP-hard problems restricted to partial k- trees
• Approximation algorithms for connected dominating sets
• Some APX-completeness results for cubic graphs
• Minimum \(k\)-path vertex cover
• Online regenerator placement
• Online Optimization of Busy Time on Parallel Machines
• The regenerator location problem
• On the Complexity of Some Colorful Problems Parameterized by Treewidth
• Graph minors. II. Algorithmic aspects of tree-width
• A linear time algorithm for finding tree-decompositions of small treewidth
• Approximation Schemes for Steiner Forest on Planar Graphs and Graphs of Bounded Treewidth
• The complexity of satisfiability problems
• Parameterized Complexity of Arc-Weighted Directed Steiner Problems