Premium
Lower bounds for two‐period grooming via linear programming duality
Author(s) -
Colbourn Charles J.,
Quattrocchi Gaetano,
Syrotiuk Violet R.
Publication year - 2008
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.20251
Subject(s) - combinatorics , traffic grooming , mathematics , graph , upper and lower bounds , integer programming , set (abstract data type) , linear programming , induced subgraph , discrete mathematics , computer science , mathematical optimization , wavelength division multiplexing , wavelength , mathematical analysis , physics , optoelectronics , vertex (graph theory) , programming language
In a problem arising in grooming for two‐period optical networks, it is required to decompose the complete graph on n vertices into subgraphs each containing at most C edges, so that the induced subgraphs on a specified set of v ≤ n vertices each contain at most C ′ < C edges. The cost of the grooming is the sum, over all subgraphs, of the number of vertices of nonzero degree in the subgraph. The optimum grooming is the one of lowest cost. An integer linear programming formulation is used to determine precise lower bounds on this minimum cost for all choices of n and v when 1 ≤ C ′ < C ≤ 3. In most cases, this approach determines not only the bound but also the specific structure of any grooming that could realize the bound. © 2008 Wiley Periodicals, Inc. NETWORKS, 2008