RNC-approximation algorithms for the steiner problem

DOI10.1007/BFB0023489MaRDI QIDQ5048954zbMATH OpenOpenAlexFDO

Authors 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) Randomized algorithms (68W20) Approximation algorithms (68W25)

Recommendations

• scientific article; zbMATH DE number 4049088
• Approximation algorithms for the covering Steiner problem
• scientific article; zbMATH DE number 1305435
• An approximation algorithm for the Steiner connectivity problem
• Approximations for the Steiner multicycle problem
• scientific article; zbMATH DE number 1445321
• A faster approximation algorithm for the Steiner problem in graphs
• A faster approximation algorithm for the Steiner problem in graphs
• Approximation Algorithms for Directed Steiner Problems
• scientific article; zbMATH DE number 1303557

Cites work

• A fast algorithm for Steiner trees
• An 11/6-approximation algorithm for the network Steiner problem
• An \(O(\log m)\) parallel algorithm for the minimum spanning tree problem
• An augmenting path algorithm for linear matroid parity
• scientific article; zbMATH DE number 3965444 (Why is no real title available?)
• scientific article; zbMATH DE number 3677874 (Why is no real title available?)
• scientific article; zbMATH DE number 3698383 (Why is no real title available?)
• scientific article; zbMATH DE number 1256636 (Why is no real title available?)
• scientific article; zbMATH DE number 1263241 (Why is no real title available?)
• Improved Approximations for the Steiner Tree Problem
• Matching is as easy as matrix inversion
• Random pseudo-polynomial algorithms for exact matroid problems
• Reducibility among combinatorial problems
• The steiner problem in graphs
• The Steiner problem with edge lengths 1 and 2
• Une heuristique pour le problème de l'arbre de Steiner

Cited in

(8)

• Recent results on approximating the Steiner tree problem and its generalizations
• An improved algorithm for the Steiner tree problem with bounded edge-length
• An Efficient Approximation Algorithm for the Steiner Tree Problem
• Approximating the Generalized Capacitated Tree-Routing Problem
• A New Approximation Algorithm for the Steiner Tree Problem with Performance Ratio 5/3
• Strong Steiner tree approximations in practice
• Definition and algorithms for reliable Steiner tree problem
• Fully dynamic algorithms for Euclidean Steiner tree

This page was built for publication: RNC-approximation algorithms for the steiner problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5048954)