Grooming traffic to minimize load

Charles Colbourn, Alan C H Ling, Gaetano Quattrocchi, Violet Syrotiuk

Research output: Contribution to journalArticlepeer-review

1 Scopus citations


Grooming traffic in optical networks can be formulated as partitioning the edges of a graph into subgraphs each having at most a specified number c of edges; a typical objective is to minimize the sum over all subgraphs of the vertices of nonzero degree (the drop cost). In practice, however, one may be constrained so that each vertex has nonzero degree in a limited number of different subgraphs of the partition. This is the load on the vertex, and the load of the grooming is the largest load at any vertex. The minimum load of a grooming for an n-vertex m-edge graph is determined here for all n, m, and c ∈ {2,3,4}. Indeed it is shown that in these cases drop cost and load can be minimized simultaneously.

Original languageEnglish (US)
Pages (from-to)536-544
Number of pages9
JournalDiscrete Mathematics
Issue number3
StatePublished - Feb 6 2012


  • Graph decompositions
  • Load minimization
  • SONET ring
  • Traffic grooming

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics


Dive into the research topics of 'Grooming traffic to minimize load'. Together they form a unique fingerprint.

Cite this