New approximation algorithms for the Steiner tree problems

DOI10.1023/A:1009758919736zbMath0895.90171OpenAlexW109985799MaRDI QIDQ1383806

Marek Karpinski, Alexander Z. Zelikovsky

Publication date: 13 April 1998

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1023/a:1009758919736

zbMATH Keywords

Steiner tree problemapproximation algorithms

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35)

Related Items (27)

Bottleneck bichromatic full Steiner trees ⋮ Geometry-experiment algorithm for Steiner minimal tree problem ⋮ Improved algorithms for joint optimization of facility locations and network connections ⋮ On the equivalence of the bidirected and hypergraphic relaxations for Steiner tree ⋮ Approximation algorithm with constant ratio for stochastic prize-collecting Steiner tree problem ⋮ Solving Steiner trees: Recent advances, challenges, and perspectives ⋮ On the approximability of the Steiner tree problem. ⋮ Approximating the Generalized Capacitated Tree-Routing Problem ⋮ A primal-dual algorithm for the generalized prize-collecting Steiner forest problem ⋮ Parameterized study of Steiner tree on unit disk graphs ⋮ Differential approximation results for the Steiner tree problem ⋮ An Efficient Approximation Algorithm for the Steiner Tree Problem ⋮ Definition and algorithms for reliable Steiner tree problem ⋮ On finding a shortest isothetic path and its monotonicity inside a digital object ⋮ An improved algorithm for the Steiner tree problem with bounded edge-length ⋮ Concurrent multicast in weighted networks ⋮ Bottleneck Steiner tree with bounded number of Steiner vertices ⋮ A partition-based relaxation for Steiner trees ⋮ The Euclidean bottleneck full Steiner tree problem ⋮ Concurrent multicast in weighted networks ⋮ Steiner trees and polyhedra ⋮ Approximations for Steiner trees with minimum number of Steiner points ⋮ Parameterized Approximation Algorithms for Bidirected Steiner Network Problems ⋮ Steiner trees in uniformly quasi-bipartite graphs. ⋮ Improved methods for approximating node weighted Steiner trees and connected dominating sets. ⋮ An approximation for minimum multicast route in optical networks with nonsplitting nodes ⋮ Multi-rooted greedy approximation of directed Steiner trees with applications

This page was built for publication: New approximation algorithms for the Steiner tree problems