Module org.jgrapht.core
Package org.jgrapht.alg.interfaces

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.