Graph Partitioning and Traffic Grooming with Bounded Degree Request Graph

Zenthao Li 1 2
2 MASCOTTE - Algorithms, simulation, combinatorics and optimization for telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
Abstract : We study a graph partitioning problem which arises from traffic grooming in optical networks. We wish to minimize the equipment cost in a SONET WDM ring network by minimizing the number of Add-Drop Multiplexers (ADMs) used. We consider the version introduced by Mu~noz and Sau~[Mu~noz and Sau, WG 08] where the ring is unidirectional with a grooming factor $C$, and we must design the network (namely, place the ADMs at the nodes) so that it can support \\emphany request graph with maximum degree at most Δ. This problem is essentially equivalent to finding the least integer $M(C,\\Delta)$ such that the edges of any graph with maximum degree at most Δ can be partitioned into subgraphs with at most $C$ edges and each vertex appears in at most $M(C,\\Delta)$ subgraphs~[Mu~noz and Sau, WG 08] . The cases where $\\Delta=2$ and $\\Delta=3,C\\neq 4$ were solved by Mu~noz and Sau~[Mu~noz and Sau, WG 08] . In this article we establish the value of $M(C,\\Delta)$ for many more cases, leaving open only the case where $\\Delta \\geq 5$ is odd, $\\Delta \\pmod2C$ is between $3$ and $C-1$, $C\\geq 4$, and the request graph does not contain a perfect matching. In particular, we answer a conjecture of~[Mu~noz and Sau, WG 08] .
Type de document :
Communication dans un congrès
35th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2009), 2009, Montpellier, France. 5911, pp.250-261, 2009, Lecture Notes in Computer Science
Liste complète des métadonnées

https://hal.inria.fr/hal-00795411
Contributeur : Alain Monteil <>
Soumis le : jeudi 28 février 2013 - 10:57:32
Dernière modification le : mercredi 14 décembre 2016 - 01:06:06

Identifiants

  • HAL Id : hal-00795411, version 1

Collections

Citation

Zenthao Li, . Graph Partitioning and Traffic Grooming with Bounded Degree Request Graph. 35th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2009), 2009, Montpellier, France. 5911, pp.250-261, 2009, Lecture Notes in Computer Science. <hal-00795411>

Partager

Métriques

Consultations de la notice

69