A New Approximation Algorithm for the Steiner Tree Problem with Performance Ratio 5/3
From MaRDI portal
Publication:4500859
DOI10.1006/jagm.2000.1086zbMath0959.68101OpenAlexW1998126097MaRDI QIDQ4500859
Hans Jürgen Prömel, Angelika Steger
Publication date: 27 August 2000
Published in: Journal of Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1006/jagm.2000.1086
Related Items (31)
Bottleneck bichromatic full Steiner trees ⋮ Improved algorithms for joint optimization of facility locations and network connections ⋮ Energy-Efficient Communication in Multi-interface Wireless Networks ⋮ On the equivalence of the bidirected and hypergraphic relaxations for Steiner tree ⋮ Approximation algorithm with constant ratio for stochastic prize-collecting Steiner tree problem ⋮ A factoring approach for the Steiner tree problem in undirected networks ⋮ Solving Steiner trees: Recent advances, challenges, and perspectives ⋮ The Clustered Selected-Internal Steiner Tree Problem ⋮ On the approximability of the Steiner tree problem. ⋮ An ETH-tight algorithm for bidirected Steiner connectivity ⋮ Energy-efficient communication in multi-interface wireless networks ⋮ Optimal relay location for resource-limited energy-efficient wireless communication ⋮ A primal-dual algorithm for the generalized prize-collecting Steiner forest problem ⋮ Parameterized study of Steiner tree on unit disk graphs ⋮ Combination algorithms for Steiner tree variants ⋮ The saga of minimum spanning trees ⋮ Bounding the payment of approximate truthful mechanisms ⋮ Genetic local search for multicast routing with pre-processing by logarithmic simulated annealing ⋮ A Weighted Linear Matroid Parity Algorithm ⋮ Weighted matching with pair restrictions ⋮ Bottleneck Steiner tree with bounded number of Steiner vertices ⋮ A partition-based relaxation for Steiner trees ⋮ The Euclidean bottleneck full Steiner tree problem ⋮ Spanning trees of 3-uniform hypergraphs ⋮ Wireless network design via 3-decompositions ⋮ Approximating Steiner trees and forests with minimum number of Steiner points ⋮ Approximating minimum-power edge-covers and 2,3-connectivity ⋮ Unnamed Item ⋮ Parameterized Approximation Algorithms for Bidirected Steiner Network Problems ⋮ Steiner trees in uniformly quasi-bipartite graphs. ⋮ An approximation algorithm for a bottleneck \(k\)-Steiner tree problem in the Euclidean plane
This page was built for publication: A New Approximation Algorithm for the Steiner Tree Problem with Performance Ratio 5/3
