PDF

Graph Decompositions and Grooming in Optical Networks (Charles J. Colbourn - Arizona State University)

In the 1970s, Jean-Claude Bermond and others pioneered the study of graph designs. Viewing balanced incomplete block designs as decompositions of a λ-fold complete graph of order v into simple complete graphs of order k underpins this generalization, in whic h decompositions of λ K_v into subgraphs each isomorphic to a graph in a target set G are studied. This powerful generalization has spawned hundreds of papers on the existence and construction of graph designs. Recently the powerful results and machinery developed for graph designs have been applied to a problem of substantial practical interest: grooming traffic in optical networks. Once again Jean-Claude has been a major force in the research on this topic. In this talk we outline some of the main directions taken on graph designs, focussing on applications to the grooming problem.