Package com.jgalgo.alg.span

Class SteinerTreeMehlhorn

java.lang.Object

com.jgalgo.alg.span.SteinerTreeAlgoAbstract

com.jgalgo.alg.span.SteinerTreeMehlhorn

All Implemented Interfaces:

SteinerTreeAlgo

public class SteinerTreeMehlhorn
extends SteinerTreeAlgoAbstract

Mehlhorn algorithm for Steiner tree approximation.

The Steiner tree problem is NP-hard, and this algorithm provides a \(2(1-1/l)\)-approximation where \(l\) is the minimum number of leaves in any Steiner tree for the given graph. Note that \(l\) is always smaller or equal to the number of terminals vertices.

The algorithm runs in \(O(m+n \log n)\) time and use linear space.

Based on 'A faster approximation algorithm for the Steiner problem in graphs' by Kurt Mehlhorn.

Author:

Barak Ugav

Nested Class Summary

Nested classes/interfaces inherited from interface com.jgalgo.alg.span.SteinerTreeAlgo

SteinerTreeAlgo.IResult, SteinerTreeAlgo.Result<V,E>

Constructor Summary

Constructors

Constructor	Description
SteinerTreeMehlhorn()	Construct a new Steiner tree algorithm object.

Method Summary

Modifier and Type	Method	Description
SteinerTreeAlgo.IResult	computeSteinerTree(IndexGraph g, IWeightFunction w, IntCollection terminals)

Methods inherited from class com.jgalgo.alg.span.SteinerTreeAlgoAbstract

computeSteinerTree

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

SteinerTreeMehlhorn

public SteinerTreeMehlhorn()

Construct a new Steiner tree algorithm object.

Please prefer using SteinerTreeAlgo.newInstance() to get a default implementation for the SteinerTreeAlgo interface.

Method Detail

computeSteinerTree

public SteinerTreeAlgo.IResult computeSteinerTree(IndexGraph g,
                                                  IWeightFunction w,
                                                  IntCollection terminals)