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

Class 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:
    SteinerTreeAlgorithm, Steiner tree problem

    • Constructor Detail

      • 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 Detail

      • 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