O problema do subgrafo biconexo mínimo generalizado: algoritmos e formulações

Abstract

Given an integer number k > 2 and an undirected simple graph G = (V; E) with positive real weights assigned to its edges, where V is partitioned into k subsets (or clusters), the Generalized Minimum Biconnected Subgraph Problem (GMBSP) amounts to nding a minimum-cost biconnected subgraph S of G, such that S contains exactly one vertex from every cluster of G. In this work, we propose an exact Branch-and-cut algorithm and some heuristics to solve PSBMG. Our Branch-and-cut algorithm separates four classes of valid inequalities for GMBSP, all of them adapted from valid inequalities for other problems related to GMBSP. In order to better assess our solution approaches, we conducted several computational experiments using dense and sparse benchmark instances. For a considerable fraction of those instances, we were able to provide new optimality certicates, as well as better upper and lower bounds.