RNC-approximation algorithms for the steiner problem

DOI10.1007/BFb0023489zbMath1498.68213OpenAlexW1485792125MaRDI QIDQ5048954

Hans Jürgen Prömel, Angelika Steger

Publication date: 9 November 2022

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bfb0023489

Mathematics Subject Classification ID

Hypergraphs (05C65) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Randomized algorithms (68W20)

Related Items

Approximating the Generalized Capacitated Tree-Routing Problem ⋮ Strong Steiner Tree Approximations in Practice ⋮ An Efficient Approximation Algorithm for the Steiner Tree Problem ⋮ Definition and algorithms for reliable Steiner tree problem ⋮ An improved algorithm for the Steiner tree problem with bounded edge-length ⋮ Recent results on approximating the Steiner tree problem and its generalizations

Cites Work

• An augmenting path algorithm for linear matroid parity
• Matching is as easy as matrix inversion
• The Steiner problem with edge lengths 1 and 2
• A fast algorithm for Steiner trees
• An \(O(\log m)\) parallel algorithm for the minimum spanning tree problem
• An 11/6-approximation algorithm for the network Steiner problem
• Random pseudo-polynomial algorithms for exact matroid problems
• Une heuristique pour le problème de l'arbre de Steiner
• Improved Approximations for the Steiner Tree Problem
• Reducibility among Combinatorial Problems
• The steiner problem in graphs
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item