A New Approximation Algorithm for the Steiner Tree Problem with Performance Ratio 5/3
From MaRDI portal
Publication:4500859
DOI10.1006/JAGM.2000.1086zbMATH Open0959.68101OpenAlexW1998126097MaRDI QIDQ4500859FDOQ4500859
Authors: 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
Recommendations
Cited In (33)
- A \((1/2+1/60)\)-approximation algorithm for maximum weight series-parallel subgraph
- An ETH-tight algorithm for bidirected Steiner connectivity
- Approximating Steiner trees and forests with minimum number of Steiner points
- The Euclidean bottleneck full Steiner tree problem
- Parameterized approximation algorithms for bidirected Steiner network problems
- Weighted linear matroid parity
- Wireless network design via 3-decompositions
- Genetic local search for multicast routing with pre-processing by logarithmic simulated annealing
- On the approximability of the Steiner tree problem.
- Bottleneck bichromatic full Steiner trees
- Spanning trees of 3-uniform hypergraphs
- The Clustered Selected-Internal Steiner Tree Problem
- Steiner trees in uniformly quasi-bipartite graphs.
- Title not available (Why is that?)
- A weighted linear matroid parity algorithm
- Bottleneck Steiner tree with bounded number of Steiner vertices
- A factoring approach for the Steiner tree problem in undirected networks
- Approximation algorithm with constant ratio for stochastic prize-collecting Steiner tree problem
- The saga of minimum spanning trees
- Improved algorithms for joint optimization of facility locations and network connections
- Solving Steiner trees: Recent advances, challenges, and perspectives
- Weighted matching with pair restrictions
- Energy-Efficient Communication in Multi-interface Wireless Networks
- On the equivalence of the bidirected and hypergraphic relaxations for Steiner tree
- Bounding the payment of approximate truthful mechanisms
- Optimal relay location for resource-limited energy-efficient wireless communication
- A partition-based relaxation for Steiner trees
- Energy-efficient communication in multi-interface wireless networks
- Combination algorithms for Steiner tree variants
- Parameterized study of Steiner tree on unit disk graphs
- Approximating minimum-power edge-covers and 2,3-connectivity
- A primal-dual algorithm for the generalized prize-collecting Steiner forest problem
- 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
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4500859)
