On the approximability of the Steiner tree problem.

DOI10.1016/S0304-3975(02)00414-0zbMath1045.68107MaRDI QIDQ1401253

Martin Thimm

Publication date: 17 August 2003

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

Lower boundsApproximabilityGadget reductionMinimum Steiner tree

Mathematics Subject Classification ID

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

Related Items (2)

The Steiner tree problem on graphs: inapproximability results ⋮ Parameterized analysis of the online priority and node-weighted Steiner tree problems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Ramanujan graphs
• The Steiner problem with edge lengths 1 and 2
• Explicit constructions of linear-sized superconcentrators
• The Steiner tree problem
• New approximation algorithms for the Steiner tree problems
• An 11/6-approximation algorithm for the network Steiner problem
• On the approximability of the traveling salesman problem (extended abstract)
• Improved Approximations for the Steiner Tree Problem
• A New Approximation Algorithm for the Steiner Tree Problem with Performance Ratio 5/3

This page was built for publication: On the approximability of the Steiner tree problem.