Edge-Partitioning Regular Graphs for Ring Traffic Grooming with a Priori Placement of the ADMs - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Journal Articles SIAM Journal on Discrete Mathematics Year : 2011

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.
No file

Dates and versions

lirmm-00736697 , version 1 (28-09-2012)

Identifiers

Cite

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, 2011, 25 (4), pp.1490-1505. ⟨10.1137/090775440⟩. ⟨lirmm-00736697⟩
112 View
0 Download

Altmetric

Share

Gmail Mastodon Facebook X LinkedIn More