Hardness and Approximation of Traffic Grooming

DOI10.1007/978-3-540-77120-3_49MaRDI QIDQ5387787zbMATH OpenOpenAlexFDO

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

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

Approximation AlgorithmsAPX-hardnessinapproximabilityOptical NetworksPTASSONET ADMTraffic Grooming

Mathematics Subject Classification ID

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

Recommendations

• Hardness and approximation of traffic grooming
• Approximating the traffic grooming problem
• Algorithms and Computation
• Approximation algorithms for grooming in optical network design
• Approximating the Traffic Grooming Problem in Tree and Star Networks

Cites work

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

Cited in

(16)

• Approximating the traffic grooming problem
• On ring grooming in optical networks
• Traffic Grooming: Combinatorial Results and Practical Resolutions
• Approximating the Traffic Grooming Problem in Tree and Star Networks
• Degree-Constrained Subgraph Problems: Hardness and Approximation Results
• Approximating the Multicast Traffic Grooming Problem in Unidirectional SONET/WDM Rings
• On the complexity and algorithm of grooming regular traffic in WDM optical networks
• Approximating the traffic grooming problem in tree and star networks
• The ring grooming problem
• On the complexity of the regenerator cost problem in general networks with traffic grooming
• Traffic Grooming in Unidirectional WDM Rings with Bounded Degree Request Graph
• Hardness and Approximation of Traffic Grooming
• On the Complexity of the Traffic Grooming Problem in Optical Networks
• Approximation algorithms for grooming in optical network design
• Algorithms and Computation
• 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 Q5387787)