On the design of networks with unicyclic connected components
- PDF / 71,123 Bytes
- 2 Pages / 439.37 x 666.142 pts Page_size
- 47 Downloads / 153 Views
On the design of networks with unicyclic connected components Makhlouf Hadji
Published online: 7 November 2012 © Springer-Verlag Berlin Heidelberg 2012
Abstract This is a summary of my PhD thesis supervised by Walid Ben-Ameur and defended on September 29 2009, at Télécom SudParis. The thesis is written in French language and is available from the author upon request at [email protected]. Given a weighted undirected graph, we want to partition the set of vertices into some connected components such that each connected component contains exactly one cycle. The objective function is given by the weight of the edges included in the solution. First, we observe that this problem is easy to solve since it is related to the bicircular matroid. Then, we add a new technical constraint related to the size of cycles: the solution should not contain cycles of length less than a certain bound. This constraint makes the problem difficult. A polyhedral study is then proposed. Many facets and valid inequalities are derived. Some of them can be exactly separated in polynomial time. We also consider another important variation of the problem. Some given special nodes must belong to cycles. We still require the connected components to be unicyclic while the cycle size constraint is ignored. It turns out that the problem is easy to solve. A non-trivial reduction to a b-matching problem is used to prove this fact. An exact extended linear formulation is provided. We also present a partial description of the convex hull of the incidence vectors of these Steiner networks. Polynomial-time separation algorithms are described. One of them is a generalization of the PadbergRao algorithm to separate blossom inequalities.
M. Hadji (B) Institut Mines-Telecom, Télécom SudParis, SAMOVAR, CNRS (UMR 5157), 09, Rue Charles Fourier, 91010 Evry, France e-mail: [email protected]
123
198
M. Hadji
Other technical constraints are proposed such as degree constraints, a bound of the number of unicyclic components, constraints related to whether some given pairs of vertices belong to the same component or to different components. Finally, the spectrum of some specified classes of unicyclic graphs is studied.
123
Data Loading...
