An 11/6-approximation algorithm for the network Steiner problem
From MaRDI portal
Publication:2366230
DOI10.1007/BF01187035zbMath0768.68192OpenAlexW2012130001MaRDI QIDQ2366230
Publication date: 29 June 1993
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf01187035
Analysis of algorithms and problem complexity (68Q25) Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (61)
Improved approximation algorithms for single-tiered relay placement ⋮ $O(\log^2{k}/\log\log{k})$-Approximation Algorithm for Directed Steiner Tree: A Tight Quasi-Polynomial Time Algorithm ⋮ RNC-approximation algorithms for the steiner problem ⋮ On greedy heuristic for Steiner minimum trees ⋮ Approximating Steiner Trees and Forests with Minimum Number of Steiner Points ⋮ DIAMETER-CONSTRAINED STEINER TREES ⋮ On component-size bounded Steiner trees ⋮ Node-weighted Steiner tree approximation in unit disk graphs ⋮ Improved algorithms for joint optimization of facility locations and network connections ⋮ A primal-dual approximation algorithm for generalized Steiner network problems ⋮ The Influence of Preprocessing on Steiner Tree Approximations ⋮ On the equivalence of the bidirected and hypergraphic relaxations for Steiner tree ⋮ A practical greedy approximation for the directed Steiner tree problem ⋮ An improved approximation scheme for the Group Steiner Problem ⋮ A Practical Greedy Approximation for the Directed Steiner Tree Problem ⋮ Solving Steiner trees: Recent advances, challenges, and perspectives ⋮ The Clustered Selected-Internal Steiner Tree Problem ⋮ On the approximability of the Steiner tree problem. ⋮ T-joins in strongly connected hypergraphs ⋮ An ETH-tight algorithm for bidirected Steiner connectivity ⋮ Approximating the Generalized Capacitated Tree-Routing Problem ⋮ O(n log n)-average-time algorithm for shortest network under a given topology ⋮ A primal-dual algorithm for the generalized prize-collecting Steiner forest problem ⋮ Minimum diameter cost-constrained Steiner trees ⋮ Combination algorithms for Steiner tree variants ⋮ Approximations for node-weighted Steiner tree in unit disk graphs ⋮ Differential approximation results for the Steiner tree problem ⋮ Strong Steiner Tree Approximations in Practice ⋮ Bounding the payment of approximate truthful mechanisms ⋮ An Efficient Approximation Algorithm for the Steiner Tree Problem ⋮ Approximations and lower bounds for the length of minimal Euclidean Steiner trees ⋮ Definition and algorithms for reliable Steiner tree problem ⋮ An improved algorithm for the Steiner tree problem with bounded edge-length ⋮ A series of approximation algorithms for the acyclic directed Steiner tree problem ⋮ Approximation Algorithms for Steiner Tree Based on Star Contractions: A Unified View ⋮ Concurrent multicast in weighted networks ⋮ Heuristics for the Steiner problem in graphs ⋮ On better heuristics for Steiner minimum trees ⋮ A simple proof of the planar rectilinear Steiner ratio ⋮ A partition-based relaxation for Steiner trees ⋮ Wireless network design via 3-decompositions ⋮ Approximating Steiner trees and forests with minimum number of Steiner points ⋮ Modifying edges of a network to obtain short subgraphs ⋮ Approximating minimum-power edge-covers and 2,3-connectivity ⋮ Multicastad hocrouting through mobility-aware Steiner tree meshes with consistency across different mobility models ⋮ Combinatorial optimization in system configuration design ⋮ Recent results on approximating the Steiner tree problem and its generalizations ⋮ New Reoptimization Techniques applied to Steiner Tree Problem ⋮ An efficient approximation algorithm for the survivable network design problem ⋮ Two Constant Approximation Algorithms for Node-Weighted Steiner Tree in Unit Disk Graphs ⋮ Parameterized Approximation Schemes for Steiner Trees with Small Number of Steiner Vertices ⋮ Parameterized Approximation Algorithms for Bidirected Steiner Network Problems ⋮ Steiner trees in uniformly quasi-bipartite graphs. ⋮ On the terminal Steiner tree problem. ⋮ Improved methods for approximating node weighted Steiner trees and connected dominating sets. ⋮ On the Clustered Steiner Tree Problem ⋮ A Faster Implementation of Zelikovsky's 11/6-Approximation Algorithm for the Steiner Problem in Graphs ⋮ Steiner Problems with Limited Number of Branching Nodes ⋮ A note on the MST heuristic for bounded edge-length Steiner trees with minimum number of Steiner points ⋮ On the clustered Steiner tree problem ⋮ Multi-rooted greedy approximation of directed Steiner trees with applications
Cites Work
This page was built for publication: An 11/6-approximation algorithm for the network Steiner problem
