Improved approximation algorithms for directed Steiner forest
From MaRDI portal
Publication:414883
DOI10.1016/j.jcss.2011.05.009zbMath1237.68246OpenAlexW2080551019MaRDI QIDQ414883
Guy Kortsarz, Moran Feldman, Zeev Nutov
Publication date: 11 May 2012
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.jcss.2011.05.009
Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)
Related Items
On minimum generalized Manhattan connections, Computing Approximate Nash Equilibria in Network Congestion Games with Polynomially Decreasing Cost Functions, Computing approximate Nash equilibria in network congestion games with polynomially decreasing cost functions, Online Buy-at-Bulk Network Design, Reachability Preservers: New Extremal Bounds and Approximation Algorithms, An ETH-tight algorithm for bidirected Steiner connectivity, Structural properties of minimum multi-source multi-sink Steiner networks in the Euclidean plane, Approximating node-connectivity augmentation problems, Solving Zero-Sum Games Using Best-Response Oracles with Applications to Search Games, ETH-Hardness of Approximating 2-CSPs and Directed Steiner Network, Approximating \(k\)-generalized connectivity via collapsing HSTs, Improved Approximation for the Directed Spanner Problem, How to Secure Matchings against Edge Failures, Approximating the generalized minimum Manhattan network problem, Approximating minimum Manhattan networks in higher dimensions, Spider Covering Algorithms for Network Design Problems, The Complexity of Contracts, Parameterized Approximation Algorithms for Bidirected Steiner Network Problems
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A series of approximation algorithms for the acyclic directed Steiner tree problem
- A factor 2 approximation algorithm for the generalized Steiner network problem
- Tight approximation algorithm for connectivity augmentation problems
- Approximating the weight of shallow Steiner trees
- A greedy approximation algorithm for the group Steiner problem
- An improved approximation scheme for the Group Steiner Problem
- Design networks with bounded pairwise distance
- Detecting high log-densities
- An improved LP-based approximation for steiner tree
- Dial a Ride from k -forest
- Approximation Algorithms for Nonuniform Buy-at-Bulk Network Design
- Approximating Directed Buy-at-Bulk Network Design
- Cost-Distance: Two Metric Network Design
- Handbook of Approximation Algorithms and Metaheuristics
- The Directed Steiner Network Problem is Tractable for a Constant Number of Terminals
- Saving an epsilon
- The prize-collecting generalized steiner tree problem via a new approach of primal-dual schema
- Approximation Schemes for the Restricted Shortest Path Problem
- A Parallel Repetition Theorem
- A Polylogarithmic Approximation Algorithm for the Group Steiner Tree Problem
- Randomized metarounding
- A General Approximation Technique for Constrained Forest Problems
- A Nearly Best-Possible Approximation Algorithm for Node-Weighted Steiner Trees
- When Trees Collide: An Approximation Algorithm for the Generalized Steiner Problem on Networks
- Approximation Algorithms for Directed Steiner Problems
- Tighter Bounds for Graph Steiner Tree Approximation
- Approximating Steiner Networks with Node-Weights
- The dense \(k\)-subgraph problem
- A simple efficient approximation scheme for the restricted shortest path problem
