Edge-Partitioning Regular Graphs for Ring Traffic Grooming with a Priori Placement of the ADMs

Xavier Muñoz 1 Zhentao Li 2 Ignasi Sau 3
3 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : We study the following graph partitioning problem: Given two positive integers $C$ and $\Delta$, find the least integer $M(C,\Delta)$ such that the edges of any graph with maximum degree at most $\Delta$ can be partitioned into subgraphs with at most $C$ edges and each vertex appears in at most $M(C,\Delta)$ subgraphs. This problem is naturally motivated by traffic grooming, which is a major issue in optical networks. Namely, we introduce a new pseudodynamic model of traffic grooming in unidirectional rings, in which the aim is to design a network able to support any request graph with a given bounded degree. We show that optimizing the equipment cost under this model is essentially equivalent to determining the parameter $M(C,\Delta)$. We establish the value of $M(C,\Delta)$ for almost all values of $C$ and $\Delta$, leaving open only the case where $\Delta \geq 5$ is odd, $\Delta \pmod{2C}$ is between $3$ and $C-1$, $C\geq 4$, and the request graph does not contain a perfect matching. For these open cases, we provide upper bounds that differ from the optimal value by at most one.
Type de document :
Article dans une revue
Siam Journal on Discrete Mathematics, Society for Industrial and Applied Mathematics, 2011, 25 (4), pp.1490-1505. 〈10.1137/090775440〉
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00736697
Contributeur : Ignasi Sau <>
Soumis le : vendredi 28 septembre 2012 - 17:53:06
Dernière modification le : vendredi 7 septembre 2018 - 14:04:02

Identifiants

Collections

Citation

Xavier Muñoz, Zhentao Li, Ignasi Sau. Edge-Partitioning Regular Graphs for Ring Traffic Grooming with a Priori Placement of the ADMs. Siam Journal on Discrete Mathematics, Society for Industrial and Applied Mathematics, 2011, 25 (4), pp.1490-1505. 〈10.1137/090775440〉. 〈lirmm-00736697〉

Partager

Métriques

Consultations de la notice

138