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.

Abstract The vitality of an arc/node of a graph with respect to the maximum flow between two fixed nodes s and t is defined as the reduction of the maximum flow caused by the removal of that arc/node. In this paper, we address the issue of determining the vitality of arcs and/or nodes for the maximum flow problem. We show how to compute the vitality of all arcs in a general undirected graph by solving only 2(n − 1) max flow instances and, in st‐planar graphs (directed or undirected) we show how to compute the vitality of all arcs and all nodes in O(n) worst‐case time. Moreover, after determining the vitality of arcs and/or nodes, and given a planar embedding of the graph, we can determine the vitality of a “contiguous” set of arcs/nodes in time proportional to the size of the set.

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

Clustering problems with relational constraints in which the underlying graph is a tree arise in a variety of applications: hierarchical data base paging, communication and distribution networks, districting, biological taxonomy, and others. They are formulated here as optimal tree partitioning problems. In a previous paper, it was shown that their computational complexity strongly depends on the nature of the objective function and, in particular, that minimizing the total within-cluster dissimilarity or the diameter is computationally hard. We propose heuristics that find good partitions within a reasonable time, even for instances of relatively large size. Such heuristics are based on the solution of continuous relaxations of certain integer (or almost integer) linear programs. Experimental results on over 2000 randomly generated instances with up to 500 entities show that the values (total within-cluster dissimilarity or diameter) of the solutions provided by these heuristics are quite close to the minimum one.

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

Abstract Given a tree T = (V, E), with |V| = n, we consider the problem of selecting a subtree with at most k leaves and with a diameter of at most l which minimizes the sum of the distances of the vertices from the selected subtree. We call such a subtree the (k, l)‐core of T. We provide two algorithms; the first one for unweighted trees has time complexity of O(n2), whereas the second one for weighted trees has time complexity of O(n2log n). The idea for both the algorithms is that, by starting from the tree T, we construct new rooted trees where the maximum length of a path is at most l. Then, for each new tree, we can apply a greedy‐type procedure to find a subtree containing the root with at most k leaves and which minimizes the sum of the distances. © 2002 Wiley Periodicals, Inc.

The partitioning of a rectangular grid graph with weighted vertices into p connected components such that the component of smallest weight is as heavy as possible (the max-min problem) is considered. It is shown that the problem is NP-hard for rectangles with at least three rows. A shifting algorithm is given which approximates the optimal solution. Bounds for the relative error are determined under a posteriori hypotheses. A further shifting algorithm is also given which allows for error estimates under a priori hypotheses and for asymptotic error estimates. A similar approach can be taken with the problem of finding the partition whose largest component is as small as possible (the min-max problem). The case of rectangles with two rows has a polynomial algorithm and is dealt with in another paper. © 1998 John Wiley & Sons, Inc. Networks 32: 115–125, 1998