V- the vertex type
E- the edge type
public class EsauWilliamsCapacitatedMinimumSpanningTree<V,E> extends AbstractCapacitatedMinimumSpanningTree<V,E>
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.
|Constructor and Description|
Constructs an Esau-Williams GRASP algorithm instance.
|Modifier and Type||Method and Description|
Computes a capacitated spanning tree.
Calculates a partition representation of the capacitated spanning tree.
public EsauWilliamsCapacitatedMinimumSpanningTree(Graph<V,E> graph, V root, double capacity, Map<V,Double> weights, int numberOfOperationsParameter)
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
public CapacitatedSpanningTreeAlgorithm.CapacitatedSpanningTree<V,E> getCapacitatedSpanningTree()
Returns a capacitated spanning tree computed by the Esau-Williams algorithm.
protected AbstractCapacitatedMinimumSpanningTree.CapacitatedSpanningTreeSolutionRepresentation getSolution()
Copyright © 2019. All rights reserved.