Hardness and approximation of traffic grooming
DOI10.1016/J.TCS.2009.04.028zbMATH Open1171.68049OpenAlexW1999464013MaRDI QIDQ837166FDOQ837166
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
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
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)
Cites Work
- Ruling Out PTAS for Graph Min‐Bisection, Dense k‐Subgraph, and Bipartite Clique
- Maximum bounded 3-dimensional matching is MAX SNP-complete
- Title not available (Why is that?)
- Some optimal inapproximability results
- The dense \(k\)-subgraph problem
- 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
- Traffic grooming on the path
- The NP-Completeness of Some Edge-Partition Problems
- The ring grooming problem
- On the Complexity of the Traffic Grooming Problem in Optical Networks
- Approximation and Online Algorithms
- Packing triangles in bounded degree graphs.
- Parameterized and Exact Computation
- Genome Rearrangements and Sorting by Reversals
- Approximating the traffic grooming problem
- Title not available (Why is that?)
- Traffic Grooming in Unidirectional WDM Rings with Bounded Degree Request Graph
- Algorithms and Computation
Cited In (13)
- The ring grooming problem
- On approximating the \(d\)-girth of a graph
- 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
- 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
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)
