Hardness and approximation of traffic grooming

DOI10.1016/j.tcs.2009.04.028zbMath1171.68049OpenAlexW1999464013MaRDI QIDQ837166

Stéphane Pérennes, Omid Amini, Ignasi Sau

Publication date: 10 September 2009

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

Full work available at URL: https://hal.inria.fr/inria-00158341v3/file/RR-groupage.pdf

zbMATH Keywords

optical networksapproximation algorithmsPTASAPX-hardnesstraffic groomingSONET ADM

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) 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)

Related Items (8)

The complexity of the unit stop number problem and its implications to other related problems ⋮ Parameterized complexity of finding small degree-constrained subgraphs ⋮ On the approximability of some degree-constrained subgraph problems ⋮ On approximating the \(d\)-girth of a graph ⋮ On the complexity of the regenerator cost problem in general networks with traffic grooming ⋮ Approximation algorithms for grooming in optical network design ⋮ On Approximating the d-Girth of a Graph ⋮ Traffic grooming in bidirectional WDM ring networks

Cites Work

• Unnamed Item
• Unnamed Item
• Maximum bounded 3-dimensional matching is MAX SNP-complete
• Approximating the traffic grooming problem
• Packing triangles in bounded degree graphs.
• Traffic grooming on the path
• On the Size of Systems of Sets Every t of which Have an SDR, with an Application to the Worst-Case Ratio of Heuristics for Packing Problems
• The NP-Completeness of Some Edge-Partition Problems
• The ring grooming problem
• Genome Rearrangements and Sorting by Reversals
• Traffic Grooming in Unidirectional WDM Rings with Bounded Degree Request Graph
• Parameterized and Exact Computation
• On the Complexity of the Traffic Grooming Problem in Optical Networks
• Some optimal inapproximability results
• Approximation and Online Algorithms
• Ruling Out PTAS for Graph Min‐Bisection, Dense k‐Subgraph, and Bipartite Clique
• Algorithms and Computation
• The dense \(k\)-subgraph problem

This page was built for publication: Hardness and approximation of traffic grooming