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

DOI10.1007/978-3-642-03367-4_8zbMATH Open1253.68355OpenAlexW1511480398WikidataQ55952583 ScholiaQ55952583MaRDI QIDQ3183443FDOQ3183443

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

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

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (10)

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

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)