Skip to Main content Skip to Navigation
Journal articles

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

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.
Document type :
Journal articles
Complete list of metadatas

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00736697
Contributor : Ignasi Sau <>
Submitted on : Friday, September 28, 2012 - 5:53:06 PM
Last modification on : Thursday, June 18, 2020 - 12:32:04 PM

Identifiers

Collections

Citation

Xavier Muñoz, Zhentao Li, Ignasi Sau Valls. 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⟩

Share

Metrics

Record views

217