## Interface CapacitatedSpanningTreeAlgorithm<V,​E>

• Type Parameters:
V - the graph vertex type
E - the graph edge type
All Known Implementing Classes:
AbstractCapacitatedMinimumSpanningTree, AhujaOrlinSharmaCapacitatedMinimumSpanningTree, EsauWilliamsCapacitatedMinimumSpanningTree

public interface CapacitatedSpanningTreeAlgorithm<V,​E>
An algorithm which computes a capacitated (minimum) spanning tree of a given connected graph with a designated root vertex. The input is a connected undirected graph G = (V, E) with a designated root r \in V, a capacity constraint K \in \mathbb{N}, a demand function d: V \rightarrow \mathbb{N} and a capacity function c: E \rightarrow \mathbb{N}. A Capacitated Minimum Spanning Tree (CMST) is a rooted minimal cost spanning tree that satisfies the capacity constraint on all trees that are connected to the designated root. That is, the sum of the demands of all vertices is smaller or equal than K. These trees build up a partition on the vertex set of the graph. The problem is NP-hard.
• ### Nested Class Summary

Nested Classes
Modifier and Type Interface Description
static interface  CapacitatedSpanningTreeAlgorithm.CapacitatedSpanningTree<V,​E>
A spanning tree.
static class  CapacitatedSpanningTreeAlgorithm.CapacitatedSpanningTreeImpl<V,​E>
Default implementation of the spanning tree interface.
• ### Method Summary

All Methods
Modifier and Type Method Description
CapacitatedSpanningTreeAlgorithm.CapacitatedSpanningTree<V,​E> getCapacitatedSpanningTree()
Computes a capacitated spanning tree.
• ### Method Detail

• #### getCapacitatedSpanningTree

CapacitatedSpanningTreeAlgorithm.CapacitatedSpanningTree<V,​E> getCapacitatedSpanningTree()
Computes a capacitated spanning tree.
Returns:
a capacitated spanning tree