Hardness and Approximation of Traffic Grooming

DOI10.1007/978-3-540-77120-3_49zbMath1193.68285OpenAlexW1506994020MaRDI QIDQ5387787

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

Publication date: 27 May 2008

Published in: Algorithms and Computation (Search for Journal in Brave)

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

zbMATH Keywords

inapproximabilityPTASAPX-hardnessSONET ADMOptical NetworksTraffic GroomingApproximation Algorithms

Mathematics Subject Classification ID

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

Related Items (3)

Traffic Grooming in Unidirectional WDM Rings with Bounded Degree Request Graph ⋮ Hardness and Approximation of Traffic Grooming ⋮ Degree-Constrained Subgraph Problems: Hardness and Approximation Results

Cites Work

• Maximum bounded 3-dimensional matching is MAX SNP-complete
• The NP-Completeness of Some Edge-Partition Problems
• The ring grooming problem
• Hardness and Approximation of Traffic Grooming
• On the Complexity of the Traffic Grooming Problem in Optical Networks
• Approximation and Online Algorithms
• Algorithms and Computation
• Algorithms and Computation
• The dense \(k\)-subgraph problem

This page was built for publication: Hardness and Approximation of Traffic Grooming