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

In the present paper, a microwave tomographic technique is used in order to analyze the effect of oil & gas platforms located in the Adriatic Sea on the radar returns of the RA-2 sensor, installed onboard the ENVISAT satellite. The study area is located in front of the Italian Adriatic coast of Ravenna harbor. The results from the analysis of waveforms show that hyperbolae are clearly visible. The tomographic reconstructions exhibit signatures corresponding to their presence. Their relationship is thought dependent on the geometric conditions. Some examples are discussed in this paper.

The drought episode that struck Middle East countries in 2007-2009 was the worst one hitting the region in more than 60 years. An analysis of rainfall and vegetation dynamics over the temporal range covering 11 hydrological seasons from September 2002 to August 2013 has been carried out by using time series of satellite data from TRMM and MODIS platforms, over the study area covering the so called Fertile Crescent: spanning from southern Turkey, Syria, and Jordan, to Iraq and western Iran. The results of this analysis, along with supportive information about surface water reserves drawn from satellite radar altimetry suggest that the intensification of activities in new agricultural areas in southern Turkey, steadily developed during the last decade, contributed to the sensible deplenishment of water resources available over the basin.

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