1.25-Approximation Algorithm for Steiner Tree Problem with Distances 1 and 2

DOI10.1007/978-3-642-03367-4_8MaRDI QIDQ3183443zbMATH OpenOpenAlexWikidataFDO

Authors Piotr Berman, Marek Karpinski, Alex Zelikovsky

Publication date 20 October 2009

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

Full work available at URL https://doi.org/10.1007/978-3-642-03367-4_8

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

Recommendations

• scientific article; zbMATH DE number 4063109
• A faster approximation algorithm for the Steiner problem in graphs
• scientific article; zbMATH DE number 742979
• Improved Approximations for the Steiner Tree Problem
• scientific article; zbMATH DE number 1445376

Cites work

• An augmenting path algorithm for linear matroid parity
• The computation of nearly minimal Steiner trees in graphs
• The Steiner problem with edge lengths 1 and 2
• Tighter Bounds for Graph Steiner Tree Approximation

Cited in

(10)

• Differential approximation results for the Steiner tree problem
• The General Steiner Tree-Star problem.
• Approximation algorithm with constant ratio for stochastic prize-collecting Steiner tree problem
• Approximation algorithm for (connected) bounded-degree deletion problem on unit disk graphs
• An improved algorithm for the Steiner tree problem with bounded edge-length
• Parameterized study of Steiner tree on unit disk graphs
• A 3/2-approximation algorithm for generalized Steiner trees in complete graphs with edge lengths 1 and 2
• An Efficient Approximation Algorithm for the Steiner Tree Problem
• APPROXIMATION ALGORITHM FOR STEINER TREE PROBLEM WITH NEIGHBOR-INDUCED COST
• An improved approximation algorithm for the partial-terminal Steiner tree problem with edge cost 1 or 2

This page was built for publication: 1.25-Approximation Algorithm for Steiner Tree Problem with Distances 1 and 2

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