Approximation Algorithms for Directed Steiner Problems
From MaRDI portal
Publication:4939606
DOI10.1006/jagm.1999.1042zbMath0937.68155OpenAlexW2009976792MaRDI QIDQ4939606
Ashish Goel, Sudipto Guha, Zuo Dai, Chandra Chekuri, To-yat Cheung, Ming Li, Moses Charikar
Publication date: 28 May 2000
Published in: Journal of Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1006/jagm.1999.1042
Trees (05C05) Nonnumerical algorithms (68W05) Graph theory (including graph drawing) in computer science (68R10)
Related Items
Bounded Degree Group Steiner Tree Problems ⋮ $O(\log^2{k}/\log\log{k})$-Approximation Algorithm for Directed Steiner Tree: A Tight Quasi-Polynomial Time Algorithm ⋮ Hardness and approximation results for packing Steiner trees ⋮ On approximating degree-bounded network design problems ⋮ Unnamed Item ⋮ On Directed Steiner Trees with Multiple Roots ⋮ Approximate \(k\)-Steiner forests via the Lagrangian relaxation technique with internal preprocessing ⋮ Computing Approximate Nash Equilibria in Network Congestion Games with Polynomially Decreasing Cost Functions ⋮ Lehman's Theorem and the Directed Steiner Tree Problem ⋮ A practical greedy approximation for the directed Steiner tree problem ⋮ On some network design problems with degree constraints ⋮ New primal-dual algorithms for Steiner tree problems ⋮ Computing approximate Nash equilibria in network congestion games with polynomially decreasing cost functions ⋮ Greedy algorithms for the profit-aware social team formation problem ⋮ Quasi-Polynomial Algorithms for Submodular Tree Orienteering and Directed Network Design Problems ⋮ Online Buy-at-Bulk Network Design ⋮ A Practical Greedy Approximation for the Directed Steiner Tree Problem ⋮ A Tight Algorithm for Strongly Connected Steiner Subgraph on Two Terminals with Demands (Extended Abstract) ⋮ Approximation algorithms for orienting mixed graphs ⋮ Heuristic and exact algorithms for minimum-weight non-spanning arborescences ⋮ Solving Steiner trees: Recent advances, challenges, and perspectives ⋮ Reachability Preservers: New Extremal Bounds and Approximation Algorithms ⋮ Navigational guidance -- a deep learning approach ⋮ Improved approximation algorithms for directed Steiner forest ⋮ Approximating node-connectivity augmentation problems ⋮ Swap-vertex based neighborhood for Steiner tree problems ⋮ The subdivision-constrained routing requests problem ⋮ Combination algorithms for Steiner tree variants ⋮ On approximation of dominating tree in wireless sensor networks ⋮ ETH-Hardness of Approximating 2-CSPs and Directed Steiner Network ⋮ Tight approximation algorithm for connectivity augmentation problems ⋮ Cost-optimal Planning, Delete Relaxation, Approximability, and Heuristics ⋮ Preprocessing for a map sectorization problem by means of mathematical programming ⋮ On the hardness of full Steiner tree problems ⋮ Approximating \(k\)-generalized connectivity via collapsing HSTs ⋮ Register loading via linear programming ⋮ A polylogarithmic approximation algorithm for 2-edge-connected dominating set ⋮ Clearing directed subgraphs by mobile agents. Variations on covering with paths ⋮ Steiner diagrams and \(k\)-star hubs ⋮ Polylogarithmic Approximation Algorithm for k-Connected Directed Steiner Tree on Quasi-Bipartite Graphs ⋮ An algorithmic framework for the exact solution of tree-star problems ⋮ A tight algorithm for strongly connected Steiner subgraph on two terminals with demands ⋮ On a class of branching problems in broadcasting and distribution ⋮ Online Node-weighted Steiner Forest and Extensions via Disk Paintings ⋮ Approximating minimum Manhattan networks in higher dimensions ⋮ Low-light trees, and tight lower bounds for Euclidean spanners ⋮ Bounded-hops power assignment in ad hoc wireless networks ⋮ Approximating the two-level facility location problem via a quasi-greedy approach ⋮ On rooted \(k\)-connectivity problems in quasi-bipartite digraphs ⋮ A note on Rooted Survivable Networks ⋮ Spider Covering Algorithms for Network Design Problems ⋮ Parameterized Complexity of Directed Steiner Tree on Sparse Graphs ⋮ Tight Bounds for Planar Strongly Connected Steiner Subgraph with Fixed Number of Terminals (and Extensions) ⋮ Inapproximability of survivable networks ⋮ Complexity of the Steiner Network Problem with Respect to the Number of Terminals ⋮ MINIMUM ENERGY BROADCAST ROUTING IN AD HOC AND SENSOR NETWORKS WITH DIRECTIONAL ANTENNAS ⋮ Combinatorial optimization in system configuration design ⋮ Approximating fault-tolerant group-Steiner problems ⋮ Unnamed Item ⋮ Efficient Black-Box Reductions for Separable Cost Sharing ⋮ Parameterized analysis of the online priority and node-weighted Steiner tree problems ⋮ Steiner Shallow-Light Trees Are Exponentially Lighter than Spanning Ones ⋮ The polymatroid Steiner problems ⋮ Parameterized Approximation Schemes for Steiner Trees with Small Number of Steiner Vertices ⋮ The General Steiner Tree-Star problem. ⋮ Unnamed Item ⋮ A greedy approximation algorithm for the group Steiner problem ⋮ On rooted \(k\)-connectivity problems in quasi-bipartite digraphs ⋮ Tight bounds on subexponential time approximation of set cover and related problems ⋮ Multi-rooted greedy approximation of directed Steiner trees with applications
