Module org.jgrapht.core
Package org.jgrapht.alg.steiner

Class KouMarkowskyBermanAlgorithm<V,E>

java.lang.Object
org.jgrapht.alg.steiner.KouMarkowskyBermanAlgorithm<V,E>
Type Parameters:
V - the graph vertex type
E - the graph edge type
All Implemented Interfaces:
SteinerTreeAlgorithm<V,E>
public class KouMarkowskyBermanAlgorithm<V,E> extends Object implements SteinerTreeAlgorithm<V,E>
Implementation of the Kou-Markowsky-Berman algorithm for computing Steiner trees.

The Kou-Markowsky-Berman algorithm is an approximation algorithm for the Steiner tree problem. It constructs a Steiner tree by first creating a complete distance graph on the Steiner points (terminals), computing a minimum spanning tree on this graph, replacing each edge with the corresponding shortest path in the original graph, and then optimizing the result.

The algorithm runs in $O(|S||V|^2)$ time and it guarantees to output a tree that spans $S$ with total distance on its edges no more than $2 (1-\frac{1}{l})$ times that of the optimal tree, where $l$ is the number of leaves in the optimal tree.

Author:
Lena Büttel
See Also:

  • Constructor Details

    • KouMarkowskyBermanAlgorithm

      public KouMarkowskyBermanAlgorithm(Graph<V,E> graph)
      Construct a new instance of the algorithm.
      Parameters:
      graph - the input graph; must be connected with non-negative edge weights
      Throws:
      NullPointerException - if the graph is null

  • Method Details

    • getSteinerTree

      public SteinerTreeAlgorithm.SteinerTree<E> getSteinerTree(Set<V> steinerPoints)
      Computes a Steiner tree using the Kou-Markowsky-Berman algorithm.

      The algorithm finds a tree that connects all the specified Steiner points (terminals) with minimum total weight, potentially using intermediate vertices not in the terminal set. The result is guaranteed to be at most twice the weight of the optimal Steiner tree.

      Specified by:
      getSteinerTree in interface SteinerTreeAlgorithm<V,E>
      Parameters:
      steinerPoints - the set of vertices (terminals) that must be connected by the Steiner tree; must not be null or empty
      Returns:
      a Steiner tree connecting all the specified vertices
      Throws:
      IllegalArgumentException - if steinerPoints is null or empty
      RuntimeException - if the graph is not connected or contains negative edge weights