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

DOI10.1007/978-3-642-03367-4_8zbMath1253.68355OpenAlexW1511480398WikidataQ55952583 ScholiaQ55952583MaRDI QIDQ3183443

Piotr Berman, Alexander Z. Zelikovsky, Marek Karpinski

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)

Related Items (6)

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 ⋮ Approximation algorithm for (connected) bounded-degree deletion problem on unit disk graphs ⋮ Parameterized study of Steiner tree on unit disk graphs ⋮ An Efficient Approximation Algorithm for the Steiner Tree Problem ⋮ An improved algorithm for the Steiner tree problem with bounded edge-length

Cites Work

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

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