Hardness and approximation of traffic grooming

DOI10.1016/J.TCS.2009.04.028MaRDI QIDQ837166zbMATH OpenOpenAlexFDO

Authors Omid Amini, Stéphane Pérennes, 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

approximation algorithmsAPX-hardnessoptical networksPTAStraffic groomingSONET ADM

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Network design and communication in computer systems (68M10)

Recommendations

• Hardness and Approximation of Traffic Grooming
• Approximating the traffic grooming problem
• Algorithms and Computation
• Traffic Grooming: Combinatorial Results and Practical Resolutions
• Approximating the traffic grooming problem in tree and star networks
• Approximating the Traffic Grooming Problem in Tree and Star Networks
• On the Complexity of the Traffic Grooming Problem in Optical Networks
• Hardness of the undirected congestion minimization problem
• Hardness of the Undirected Congestion Minimization Problem

Cites work

• scientific article; zbMATH DE number 5130679 (Why is no real title available?)
• scientific article; zbMATH DE number 2203240 (Why is no real title available?)
• Algorithms and Computation
• Approximating the traffic grooming problem
• Approximation and Online Algorithms
• Genome Rearrangements and Sorting by Reversals
• Maximum bounded 3-dimensional matching is MAX SNP-complete
• On the Complexity of the Traffic Grooming Problem in Optical Networks
• 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
• Packing triangles in bounded degree graphs.
• Parameterized and Exact Computation
• Ruling Out PTAS for Graph Min‐Bisection, Dense k‐Subgraph, and Bipartite Clique
• Some optimal inapproximability results
• The NP-Completeness of Some Edge-Partition Problems
• The dense \(k\)-subgraph problem
• The ring grooming problem
• Traffic Grooming in Unidirectional WDM Rings with Bounded Degree Request Graph
• Traffic grooming on the path

Cited in

(16)

• The ring grooming problem
• On approximating the \(d\)-girth of a graph
• Approximating the Multicast Traffic Grooming Problem in Unidirectional SONET/WDM Rings
• Approximation algorithms for grooming in optical network design
• On Approximating the d-Girth of a Graph
• The complexity of the unit stop number problem and its implications to other related problems
• Traffic grooming in bidirectional WDM ring networks
• Traffic Grooming in Star Networks via Matching Techniques
• On ring grooming in optical networks
• Traffic Grooming: Combinatorial Results and Practical Resolutions
• Approximating the Traffic Grooming Problem in Tree and Star Networks
• Algorithms and Computation
• Parameterized complexity of finding small degree-constrained subgraphs
• On the approximability of some degree-constrained subgraph problems
• On the complexity of the regenerator cost problem in general networks with traffic grooming
• Hardness and Approximation of Traffic Grooming

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

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