turkmath.org

A G-design of order n is a decomposition of the complete graph on n vertices into edgedisjoint subgraphs isomorphic to G. Grooming uniform all-to-all traffic in optical (SONET or SDH) ring networks with grooming ratio C requires the determination of a decomposition of the complete graph on n vertices into subgraphs each having at most C edges. The drop cost of such a grooming is the total number of vertices of nonzero degree in these subgraphs, and the grooming is optimal when the drop cost is minimum. In this talk, I will talk about the connection between graph decompositions and optimal groomings, and give some new results.