Abstract 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.

We consider a connected graph G with n vertices, p of which are centers, while the remaining ones are units. For each unit‐center pair, there is a fixed assignment cost and for each vertex there is a nonnegative weight. In this article, we study the problem of partitioning G into p connected components such that each component contains exactly one center (p‐centered partition). We analyze different optimization problems of this type by defining different objective functions based on the assignment costs, or on the vertices' weights, or on both of them. For these problems, we show that they are NP‐hard on very special classes of graphs, and for some of them we provide polynomial time algorithms when G is a tree. © 2015 Wiley Periodicals, Inc. NETWORKS, Vol. 67(1), 69–81 2016

Abstract Researchers in the area of electoral systems have recently turned their attention to network flow techniques with the aim to resolve certain practically relevant problems arising in this area. The aim of this paper is to review some of this work, showing the applicability of these techniques even to problems of a very different nature. Major emphasis will be placed on “biproportional apportionment,” a problem that frequently arises in proportional electoral systems, but which in some countries is still ill‐solved, or not dealt with rigorously, notwithstanding the availability of several sound solution procedures and their concrete application in some real‐life elections. Besides biproportional apportionment, we shall discuss applications of network flows to problems such as vote transitions and political districting. Finally, we address the so‐called “give‐up problem,” which arises in the current elections for the Italian Parliament. It is related to the possible assignment of seats to multiple winners of a given party. Based on the results and techniques presented in this article, it is fair to state that network flow models and algorithms are indeed very flexible and effective tools for the analysis and the design of contemporary electoral systems. © 2011 Wiley Periodicals, Inc. NETWORKS, 2012

Abstract In this article, we study the median path problem without length restrictions on the class of connected outerplanar graphs, assuming that weights equal to 1 are assigned to the edges of a graph G, and nonnegative weights are associated to its vertices. We provide an $O(kn)$ time algorithm, where n is the number of vertices of G and k is the number of blocks in G. As a byproduct, when G is a biconnected outerplanar graph, we provide a linear time algorithm to find a median path between two fixed vertices of G without restrictions on the length. In the literature, we did not find polynomial time algorithms for this problem on such classes of graphs. © 2011 Wiley Periodicals, Inc. NETWORKS, 2011

Abstract This work studies the problem of finding optimal paths with respect to the center, median and centdian objective functions, on networks with uncertain vertex weights that are given as intervals. Our approach looks for minimax regret paths which minimize the worst‐case opportunity loss in the corresponding objective function. These problems are NP‐hard on general graphs, therefore we study them on trees. We show that a discrete optimal path always exists for each of them, and provide polynomial time solution algorithms. © 2011 Wiley Periodicals, Inc. NETWORKS, 2011

Abstract In this article we consider the problem of locating path‐shaped facilities on a tree network, minimizing the variance objective function. This type of objective is generally adopted in location problems arising in public sector applications, such as the location of evacuation or mass transit routes. We consider a weighted tree, in which a positive weight is assigned to each vertex of the tree, and positive real lengths are associated with its edges. We study the general case in which the path is continuous, that is, the end points of the optimal path can be either vertices, or points along an edge, and there is an upper bound on the length of the path. Given a tree with n vertices, for this problem we provide an O(n2) algorithm, and we show how it can be applied, with the same complexity, to the discrete case, that is, when the end points of the optimal path are vertices of the tree. We improve the previous best complexity bound in (Cáceres et al., Discr Appl Math 145 (2004), 72–79), for the unrestricted length continuous path‐variance problem, by a factor of log n. We also show that the optimal point for the variance objective function does not satisfy any nestedness property with respect to the optimal path in the unconstrained (discrete or continuous) version of the problem. © 2008 Wiley Periodicals, Inc. NETWORKS, 2009

Abstract This paper deals with the following graph partitioning problem. Consider a connected graph with n nodes, p of which are centers, while the remaining ones are units. For each unit‐center pair there is a fixed service cost and the goal is to find a partition into connected components such that each component contains only one center and the total service cost is minimum. This problem is known to be NP‐hard on general graphs, and here we show that it remains such even if the service cost is monotone and the graph is bipartite. However, in this paper we derive some polynomial time algorithms for trees. For this class of graphs we provide several reformulations of the problem as integer linear programs proving the integrality of the corresponding polyhedra. As a consequence, the tree partitioning problem can be solved in polynomial time either by linear programming or by suitable convex nondifferentiable optimization algorithms. Moreover, we develop a dynamic programming algorithm, whose recursion is based on sequences of minimum weight closure problems, which solves the problem on trees in O(np) time. © 2007 Wiley Periodicals, Inc. NETWORKS, 2008