Capacitated minimum spanning tree

Last updated

Capacitated minimum spanning tree is a minimal cost spanning tree of a graph that has a designated root node and satisfies the capacity constraint . The capacity constraint ensures that all subtrees (maximal subgraphs connected to the root by a single edge) incident on the root node have no more than nodes. If the tree nodes have weights, then the capacity constraint may be interpreted as follows: the sum of weights in any subtree should be no greater than . The edges connecting the subgraphs to the root node are called gates. Finding the optimal solution is NP-hard. [1]

Contents

Algorithms

Suppose we have a graph , with a root . Let be all other nodes in . Let be the edge cost between vertices and which form a cost matrix .

Esau-Williams heuristic

Esau-Williams heuristic finds suboptimal CMST that are very close to the exact solutions, but on average EW produces better results than many other heuristics.

Initially, all nodes are connected to the root (star graph) and the network's cost is ; each of these edges is a gate. At each iteration, we seek the closest neighbor for every node in and evaluate the tradeoff function: . We look for the greatest among the positive tradeoffs and, if the resulting subtree does not violate the capacity constraints, remove the gate connecting the -th subtree to by an edge . We repeat the iterations until we can not make any further improvements to the tree.

Esau-Williams heuristics for computing a suboptimal CMST:

function CMST(c,C,r):     T = {, , ..., }     while have changes:         for each node  = closest node in a different subtree              =  - t_max = max()         k = i such that  = t_max         if ( cost(i) + cost(j) <= c)             T = T - T = T union returnT

It is easy to see that EW finds a solution in polynomial time.

[2]

Ahuja's heuristic

Ahuja's heuristic [3] uses a local search in a large multi-exchange neighborhood from a randomized greedy initial solution.

Initial solution

The initial solution is found by using a randomized version of Esau-Williams. Randomization is achieved by executing a uniformly random join from the best ones instead of the best one in each step.

Local Search Neighborhood

Let be the initial solution with root . The neighborhood consists of any combination of a single node or subtree (general subtrees, not as in the introduction of this article) displacing one in a different component of such that the displaced structure is the next displacer, the last displacer displaces the first displacer, no original component has more than one displacer and the capacity is not exceeded in any resulting component.

Improvement Graph

An improvement graph is a tool to search a very large neighborhood efficiently. Paths through an improvement graph correspond to changes to a solution and the cost of the path is the change in the cost of the solution when applying the change. Here the improvement graph is a directed multigraph built by using 2 copies of each node and up to 4 edges from any node to any node in a different component of . The edge corresponds to the change of removing the node from its original component and replacing the subtree rooted at in the target component. Combining nodes and subtrees yields the 4 possible edges. An edge exists if the corresponding change does not lead to the target component exceeding the capacity. The cost of an edge is the difference in the cost of the minimal spanning trees on the vertices in the target component before and after the displacement. Thus neighbors in the local search correspond to cycles in the improvement graph that contain at most one node from each component.

Local Search Step

The local search step uses a dynamic programming approach to find a minimum cost cycle in the improvement graph. Paths through the improvement graph with increasing length are generated and only the most favorable with the same start and end as well as involved components is stored. To this end a hash table with the tuple of those 3 properties as key is used to hold paths. Since in each negative cycle there is a node such that all paths within that cycle containing this node have negative cost, only paths with negative cost need to be considered at all. As the comparison of sets of involved components between paths is one of the most common operations in the algorithm, it is implemented as comparison of indicator bit arrays stored as integers for speed. This however clearly stems from a lot of hash collisions, which might be a consequence of the particular choice of hash function and table structure, as well as high load factor due to space restrictions (paper from 2003).

Performance

At the time the paper was written (2003) this algorithm was state of the art on a standard operations research benchmark. The execution was dominated by the building (respectively updating) of the improvement graph. The number of edges in the improvement graph empirically scaled quadratically with the size of the input graph and since this determines the number of times the comparatively complex step of finding a minimum spanning tree has to be run, this is the most critical factor. Thus one can conclude that less dense input graphs greatly benefit the running time, as this reduces the number of edges in the improvement graph.

Applications

CMST problem is important in network design: when many terminal computers have to be connected to the central hub, the star configuration is usually not the minimum cost design. Finding a CMST that organizes the terminals into subnetworks can lower the cost of implementing a network.

Related Research Articles

<span class="mw-page-title-main">Travelling salesman problem</span> NP-hard problem in combinatorial optimization

The travelling salesman problem, also known as the travelling salesperson problem (TSP), asks the following question: "Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city?" It is an NP-hard problem in combinatorial optimization, important in theoretical computer science and operations research.

<span class="mw-page-title-main">Minimum spanning tree</span> Least-weight tree connecting graph vertices

A minimum spanning tree (MST) or minimum weight spanning tree is a subset of the edges of a connected, edge-weighted undirected graph that connects all the vertices together, without any cycles and with the minimum possible total edge weight. That is, it is a spanning tree whose sum of edge weights is as small as possible. More generally, any edge-weighted undirected graph has a minimum spanning forest, which is a union of the minimum spanning trees for its connected components.

<span class="mw-page-title-main">Prim's algorithm</span> Method for finding minimum spanning trees

In computer science, Prim's algorithm is a greedy algorithm that finds a minimum spanning tree for a weighted undirected graph. This means it finds a subset of the edges that forms a tree that includes every vertex, where the total weight of all the edges in the tree is minimized. The algorithm operates by building this tree one vertex at a time, from an arbitrary starting vertex, at each step adding the cheapest possible connection from the tree to another vertex.

<span class="mw-page-title-main">Tree decomposition</span> Mapping of a graph into a tree

In graph theory, a tree decomposition is a mapping of a graph into a tree that can be used to define the treewidth of the graph and speed up solving certain computational problems on the graph.

This is a glossary of graph theory. Graph theory is the study of graphs, systems of nodes or vertices connected in pairs by lines or edges.

<span class="mw-page-title-main">Maximum flow problem</span> Computational problem in graph theory

In optimization theory, maximum flow problems involve finding a feasible flow through a flow network that obtains the maximum possible flow rate.

<span class="mw-page-title-main">Bridge (graph theory)</span> Edge in node-link graph whose removal would disconnect the graph

In graph theory, a bridge, isthmus, cut-edge, or cut arc is an edge of a graph whose deletion increases the graph's number of connected components. Equivalently, an edge is a bridge if and only if it is not contained in any cycle. For a connected graph, a bridge can uniquely determine a cut. A graph is said to be bridgeless or isthmus-free if it contains no bridges.

<span class="mw-page-title-main">Vehicle routing problem</span> Optimization problem

The vehicle routing problem (VRP) is a combinatorial optimization and integer programming problem which asks "What is the optimal set of routes for a fleet of vehicles to traverse in order to deliver to a given set of customers?" It generalises the travelling salesman problem (TSP). It first appeared in a paper by George Dantzig and John Ramser in 1959, in which the first algorithmic approach was written and was applied to petrol deliveries. Often, the context is that of delivering goods located at a central depot to customers who have placed orders for such goods. The objective of the VRP is to minimize the total route cost. In 1964, Clarke and Wright improved on Dantzig and Ramser's approach using an effective greedy algorithm called the savings algorithm.

A link/cut tree is a data structure for representing a forest, a set of rooted trees, and offers the following operations:

Arc routing problems (ARP) are a category of general routing problems (GRP), which also includes node routing problems (NRP). The objective in ARPs and NRPs is to traverse the edges and nodes of a graph, respectively. The objective of arc routing problems involves minimizing the total distance and time, which often involves minimizing deadheading time, the time it takes to reach a destination. Arc routing problems can be applied to garbage collection, school bus route planning, package and newspaper delivery, deicing and snow removal with winter service vehicles that sprinkle salt on the road, mail delivery, network maintenance, street sweeping, police and security guard patrolling, and snow ploughing. Arc routings problems are NP hard, as opposed to route inspection problems that can be solved in polynomial-time.

<span class="mw-page-title-main">David Shmoys</span> American mathematician

David Bernard Shmoys is a Professor in the School of Operations Research and Information Engineering and the Department of Computer Science at Cornell University. He obtained his Ph.D. from the University of California, Berkeley in 1984. His major focus has been in the design and analysis of algorithms for discrete optimization problems.

In graph theory, a Trémaux tree of an undirected graph is a type of spanning tree, generalizing depth-first search trees. They are defined by the property that every edge of connects an ancestor–descendant pair in the tree. Trémaux trees are named after Charles Pierre Trémaux, a 19th-century French author who used a form of depth-first search as a strategy for solving mazes. They have also been called normal spanning trees, especially in the context of infinite graphs.

<span class="mw-page-title-main">Top tree</span> Data structure

A top tree is a data structure based on a binary tree for unrooted dynamic trees that is used mainly for various path-related operations. It allows simple divide-and-conquer algorithms. It has since been augmented to maintain dynamically various properties of a tree such as diameter, center and median.

Irrigation games are cooperative games which model cost sharing problems on networks. The irrigation game is a transferable utility game assigned to a cost-tree problem. A common example of this cost-tree problems are the irrigation networks. The irrigation ditch is represented by a graph, its nodes are water users, the edges are sections of the ditch. There is a cost of maintaining the ditch, and we are looking for the fair division of the costs among the users. The irrigation games are mentioned first by Aadland and Kolpin 1998, but the formal concept and the characterization of the game class is introduced by Márkus et al. 2011.

In graph theory, Yen's algorithm computes single-source K-shortest loopless paths for a graph with non-negative edge cost. The algorithm was published by Jin Y. Yen in 1971 and employs any shortest path algorithm to find the best path, then proceeds to find K − 1 deviations of the best path.

In mathematics, a minimum bottleneck spanning tree (MBST) in an undirected graph is a spanning tree in which the most expensive edge is as cheap as possible. A bottleneck edge is the highest weighted edge in a spanning tree. A spanning tree is a minimum bottleneck spanning tree if the graph does not contain a spanning tree with a smaller bottleneck edge weight. For a directed graph, a similar problem is known as Minimum Bottleneck Spanning Arborescence (MBSA).

In computer science, an optimal binary search tree (Optimal BST), sometimes called a weight-balanced binary tree, is a binary search tree which provides the smallest possible search time (or expected search time) for a given sequence of accesses (or access probabilities). Optimal BSTs are generally divided into two types: static and dynamic.

In computing and graph theory, a dynamic connectivity structure is a data structure that dynamically maintains information about the connected components of a graph.

Mega-merger is a distributed algorithm aimed at solving the election problem in generic connected undirected graph.

In graph theory a minimum spanning tree (MST) of a graph with and is a tree subgraph of that contains all of its vertices and is of minimum weight.

References

  1. Jothi, Raja; Raghavachari, Balaji (2005), "Approximation Algorithms for the Capacitated Minimum Spanning Tree Problem and Its Variants in Network Design", ACM Trans. Algorithms, 1 (2): 265–282, doi:10.1145/1103963.1103967, S2CID   8302085
  2. Esau, L.R.; Williams, K.C. (1966). "On teleprocessing network design: Part II. A method for approximating the optimal network". IBM Systems Journal. 5 (3): 142–147. doi:10.1147/sj.53.0142.
  3. Ahuja, R.K.; Orlin, J.B.; Sharma, D. (2003). "A composite very large-scale neighborhood structure for the capacitated minimum spanning tree problem". Operations Research Letters. 31 (3): 185–194. doi:10.1016/S0167-6377(02)00236-5.