Class EsauWilliamsCapacitatedMinimumSpanningTree<V,​E>

  • Type Parameters:
    V - the vertex type
    E - the edge type
    All Implemented Interfaces:

    public class EsauWilliamsCapacitatedMinimumSpanningTree<V,​E>
    extends AbstractCapacitatedMinimumSpanningTree<V,​E>
    Implementation of a randomized version of the Esau-Williams heuristic, a greedy randomized adaptive search heuristic (GRASP) for the capacitated minimum spanning tree (CMST) problem. It calculates a suboptimal CMST. The original version can be found in L. R. Esau and K. C. Williams. 1966. On teleprocessing system design: part II a method for approximating the optimal network. IBM Syst. J. 5, 3 (September 1966), 142-147. DOI= This implementation runs in polynomial time O(|V|^3).

    This implementation is a randomized version described in Ahuja, Ravindra K., Orlin, James B., and Sharma, Dushyant, (1998). New neighborhood search structures for the capacitated minimum spanning tree problem, No WP 4040-98. Working papers, Massachusetts Institute of Technology (MIT), Sloan School of Management.

    This version runs in polynomial time dependent on the number of considered operations per iteration numberOfOperationsParameter (denoted by p), such that runs is in $O(|V|^3 + p|V|) = O(|V|^3)$ since $p \leq |V|$.

    A Capacitated Minimum Spanning Tree (CMST) is a rooted minimal cost spanning tree that satisfies the capacity constrained on all trees that are connected to the designated root. The problem is NP-hard.

    July 12, 2018
    Christoph GrĂ¼ne
    • Constructor Detail

      • EsauWilliamsCapacitatedMinimumSpanningTree

        public EsauWilliamsCapacitatedMinimumSpanningTree​(Graph<V,​E> graph,
                                                          V root,
                                                          double capacity,
                                                          Map<V,​Double> weights,
                                                          int numberOfOperationsParameter)
        Constructs an Esau-Williams GRASP algorithm instance.
        graph - the graph
        root - the root of the CMST
        capacity - the capacity constraint of the CMST
        weights - the weights of the vertices
        numberOfOperationsParameter - the parameter how many best vertices are considered in the procedure