Open
Graph Drawing
Framework

 v. 2023.09 (Elderberry)
 

Steiner Trees

Algorithms for computing Steiner trees. More...

Classes

class  ogdf::MinSteinerTreeDirectedCut< T >
 This class implements the Directed Cut Integer Linear Program for the Steiner tree problem. More...
 
class  ogdf::MinSteinerTreeDualAscent< T >
 Dual ascent heuristic for the minimum Steiner tree problem. More...
 
class  ogdf::MinSteinerTreeGoemans139< T >
 This class implements the (1.39+epsilon)-approximation algorithm for the Steiner tree problem by Goemans et. More...
 
class  ogdf::MinSteinerTreeKou< T >
 This class implements the Minimum Steiner Tree 2-approximation algorithm by Kou et al. More...
 
class  ogdf::MinSteinerTreeMehlhorn< T >
 This class implements the Minimum Steiner Tree 2-approximation algorithm by Mehlhorn. More...
 
class  ogdf::MinSteinerTreePrimalDual< T >
 Primal-Dual approximation algorithm for Steiner tree problems. More...
 
class  ogdf::MinSteinerTreeRZLoss< T >
 This class implements the loss-contracting (1.55+epsilon)-approximation algorithm for the Steiner tree problem by Robins and Zelikovsky. More...
 
class  ogdf::MinSteinerTreeShore< T >
 Implementation of Shore, Foulds and Gibbons exact branch and bound algorithm for solving Steiner tree problems. More...
 
class  ogdf::MinSteinerTreeTakahashi< T >
 This class implements the minimum Steiner tree 2-approximation algorithm by Takahashi and Matsuyama with improvements proposed by Poggi de Aragao et al. More...
 
class  ogdf::MinSteinerTreeZelikovsky< T >
 This class implements the 11/6-approximation algorithm by Zelikovsky for the minimum Steiner tree problem along with variants and practical improvements. More...
 
class  ogdf::SteinerTreeLowerBoundDualAscent< T >
 Implementation of a dual-ascent-based lower bound heuristic for Steiner tree problems. More...
 
class  ogdf::SteinerTreePreprocessing< T >
 This class implements preprocessing strategies for the Steiner tree problem. More...
 

Detailed Description

Algorithms for computing Steiner trees.