Justo Puerto

This article deals with the problem of partitioning a graph into connected components by optimizing some balancing objective functions related to the vertex weights. Objective functions based on the gap or range of the partition's components, that is, the difference between the maximum and minimum weight of a vertex in the component, have been already introduced in the literature. Here we introduce the notion of aggregated gap , defined as the sum of the differences between the weights of the vertices and the minimum weight of a vertex in the component. We study new connected ‐partitioning problems whose objective is a function of the components' aggregated gap, and give NP‐hardness results for these problems on general graphs. Mathematical programming formulations are proposed for these problems adopting flow‐based constraints for modeling connectivity in a partition. Even if they are introduced for the new aggregated gap problems, such formulations are rather general and apply also to the classical non‐aggregated gap problems. Extensive computational tests, both for aggregated and non‐aggregated gap problems, are performed on a set of squared grids and randomly generated graphs with up to 120 vertices, and a number of components ranging from 2 to 9. In our experiments, we test several alternative formulations for our problems providing a comparative analysis of their performance.

This paper presents a new two‐phase algorithm for the bi‐objective minimum spanning tree (BMST) problem. In the first phase, it computes the extreme supported efficient solutions resorting to both mathematical programming and algorithmic approaches, while the second phase is devoted to obtaining the remaining efficient solutions (non‐extreme supported and non‐supported). This latter phase is based on a new recursive procedure capable of generating all the spanning trees of a connected graph through edge interchanges based on increasing evaluation of non‐zero reduced costs of associated weighted linear programs. Such a procedure exploits a common property of a wider class of problems to which the minimum spanning tree (MST) problem belongs, that is the spanning tree structure of its basic feasible solutions. Computational experiments are conducted on different families of graphs and with different types of cost. These results show that this new two‐phase algorithm is correct, very easy to implement and it allows one to extract conclusions on the difficulty of finding the entire set of Pareto solutions of the BMST problem depending on the graph topology and the possible correlation of the edge costs.