Hardness and approximation of traffic grooming

DOI10.1016/j.tcs.2009.04.028zbMath1171.68049MaRDI QIDQ837166

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

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

optical networks; approximation algorithms; PTAS; APX-hardness; traffic grooming; SONET ADM

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68M10: Network design and communication in computer systems

68R10: Graph theory (including graph drawing) in computer science

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

68W25: Approximation algorithms