On the approximability of the Steiner tree problem

DOI10.1007/3-540-44683-4_59MaRDI QIDQ4779183zbMATH OpenFDO

Authors Martin Thimm

Publication date 25 November 2002

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

Full work available at URL http://link.springer.de/link/service/series/0558/bibs/2136/21360678

zbMATH Keywords

approximabilitygadget reductionlower boundsminimum Steiner tree

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• On the approximability of the Steiner tree problem.
• scientific article; zbMATH DE number 2089220
• The Steiner tree problem on graphs: inapproximability results
• scientific article; zbMATH DE number 742979
• scientific article; zbMATH DE number 2044939

Cited in

(38)

• A note on the terminal Steiner tree problem
• The role of Steiner hulls in the solution to Steiner tree problems
• The Steiner tree problem. I: Formulations, compositions and extensions and extension of facets
• On the approximability of the Steiner tree problem.
• Differential approximation results for the Steiner tree problem
• Recent results on approximating the Steiner tree problem and its generalizations
• Steiner trees in uniformly quasi-bipartite graphs.
• On the terminal Steiner tree problem.
• Approximate \(k\)-MSTs and \(k\)-Steiner trees via the primal-dual method and Lagrangean relaxation
• The internal Steiner tree problem: Hardness and approximations
• On the restricted 1-Steiner tree problem
• On the edge capacitated Steiner tree problem
• On the clustered Steiner tree problem
• Approximations for two variants of the Steiner tree problem in the Euclidean plane \(\mathbb R^2\)
• scientific article; zbMATH DE number 2089220 (Why is no real title available?)
• Analysis of Steiner subtrees of random trees for traceroute algorithms
• scientific article; zbMATH DE number 426374 (Why is no real title available?)
• An Efficient Approximation Algorithm for the Steiner Tree Problem
• Universal approximations for TSP, Steiner tree, and set cover
• Approximating Buy-at-Bulk and Shallow-Light k-Steiner Trees
• On the approximability of dense Steiner problems
• scientific article; zbMATH DE number 125502 (Why is no real title available?)
• scientific article; zbMATH DE number 2044939 (Why is no real title available?)
• An approximation scheme for some Steiner tree problems in the plane
• scientific article; zbMATH DE number 776081 (Why is no real title available?)
• scientific article; zbMATH DE number 1424548 (Why is no real title available?)
• scientific article; zbMATH DE number 5042868 (Why is no real title available?)
• scientific article; zbMATH DE number 7053305 (Why is no real title available?)
• scientific article; zbMATH DE number 7053371 (Why is no real title available?)
• On Hop-Constrained Steiner Trees in Tree-Like Metrics
• A comparison of Steiner tree relaxations
• A note on computational aspects of the Steiner traveling salesman problem
• Approximations for the Steiner multicycle problem
• On better heuristics for Steiner minimum trees
• On efficient implementation of an approximation algorithm for the Steiner tree problem
• Comments on Bern's probabilistic results on rectilinear Steiner trees
• The Steiner tree problem on graphs: inapproximability results
• Approximating the selected-internal Steiner tree

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

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