Minimum‐weight subgraphs with unicyclic components and a lower‐bounded girth
Walid Ben‐Ameur, Makhlouf Hadji, Adam Ouorou · Networks · 2013
Abstract This article focuses on the problem of computing a minimum‐weight subgraph with unicyclic connected components. Although this problem is generally easy, it becomes difficult when a girth constraint is added. A polyhedral study is proposed. Many facets and valid inequalities are derived. Some of them can be exactly separated in polynomial time. Hence, the problem is solved by a cutting‐plane algorithm based on these inequalities and using a compact formulation derived from the transversality of the bicircular matroid. Numerical results are also presented. © 2012 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq, 2013