Approximation algorithms for grooming in optical network design

DOI10.1016/j.tcs.2011.03.034zbMath1216.68044OpenAlexW2051874014MaRDI QIDQ551206

Lisa Zhang, Spyridon Antonakopoulos

Publication date: 14 July 2011

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

Full work available at URL: https://doi.org/10.1016/j.tcs.2011.03.034

zbMATH Keywords

approximation algorithmscycle packingtraffic groomingoptical network

Mathematics Subject Classification ID

Network design and communication in computer systems (68M10) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

Related Items

Maximum cycle packing in Eulerian graphs using local traces

Cites Work

• Unnamed Item
• Unnamed Item
• Hardness and approximation of traffic grooming
• Better bounds for minimizing SONET ADMs
• Optimization, approximation, and complexity classes
• Pattern matching with address errors
• The NP-Completeness of Some Edge-Partition Problems
• Sorting Permutations by Reversals and Eulerian Cycle Decompositions
• Packing cycles in undirected graphs
• The SONET edge‐partition problem
• Approximation algorithms and hardness results for cycle packing problems
• Approximability of Packing Disjoint Cycles
• Approximation algorithms for the design of SDH/SONET networks
• On the Cost of Interchange Rearrangement in Strings