Improved approximation algorithms for directed Steiner forest
From MaRDI portal
Publication:414883
DOI10.1016/J.JCSS.2011.05.009zbMATH Open1237.68246OpenAlexW2080551019MaRDI QIDQ414883FDOQ414883
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
Recommendations
Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)
Cites Work
- Approximation Schemes for the Restricted Shortest Path Problem
- A simple efficient approximation scheme for the restricted shortest path problem
- Approximating the weight of shallow Steiner trees
- A greedy approximation algorithm for the group Steiner problem
- Detecting high log-densities, an \(O(n^{1/4})\) approximation for densest \(k\)-subgraph
- A Polylogarithmic Approximation Algorithm for the Group Steiner Tree Problem
- Title not available (Why is that?)
- A General Approximation Technique for Constrained Forest Problems
- Approximation Algorithms for Directed Steiner Problems
- Tighter Bounds for Graph Steiner Tree Approximation
- The dense \(k\)-subgraph problem
- A series of approximation algorithms for the acyclic directed Steiner tree problem
- An improved LP-based approximation for Steiner tree
- Handbook of Approximation Algorithms and Metaheuristics
- A Nearly Best-Possible Approximation Algorithm for Node-Weighted Steiner Trees
- When Trees Collide: An Approximation Algorithm for the Generalized Steiner Problem on Networks
- Cost-Distance: Two Metric Network Design
- Saving an epsilon
- A Parallel Repetition Theorem
- Title not available (Why is that?)
- A factor 2 approximation algorithm for the generalized Steiner network problem
- An improved approximation scheme for the Group Steiner Problem
- A deterministic algorithm for the cost-distance problem
- Approximating Steiner Networks with Node-Weights
- Dial a Ride from k -forest
- Randomized metarounding
- Design networks with bounded pairwise distance
- Approximation Algorithms for Nonuniform Buy-at-Bulk Network Design
- Approximating Directed Buy-at-Bulk Network Design
- The Directed Steiner Network Problem is Tractable for a Constant Number of Terminals
- Title not available (Why is that?)
- The prize-collecting generalized steiner tree problem via a new approach of primal-dual schema
- Tight approximation algorithm for connectivity augmentation problems
Cited In (22)
- How to Secure Matchings against Edge Failures
- An ETH-tight algorithm for bidirected Steiner connectivity
- On minimum generalized Manhattan connections
- Improved Approximation for the Directed Spanner Problem
- Stronger MIP formulations for the Steiner forest problem
- Approximating the generalized minimum Manhattan network problem
- Online Buy-at-Bulk Network Design
- Approximating minimum Manhattan networks in higher dimensions
- Computing Approximate Nash Equilibria in Network Congestion Games with Polynomially Decreasing Cost Functions
- 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
- Spider Covering Algorithms for Network Design Problems
- An FPT algorithm in polynomial space for the directed Steiner tree problem with limited number of diffusing nodes
- Improved Approximation Algorithm for Steiner k -Forest with Nearly Uniform Weights
- The Complexity of Contracts
- The parameterized complexity of the survivable network design problem
- Parameterized Approximation Algorithms for Bidirected Steiner Network Problems
- ETH-Hardness of Approximating 2-CSPs and Directed Steiner Network
- Approximating \(k\)-generalized connectivity via collapsing HSTs
- Reachability Preservers: New Extremal Bounds and Approximation Algorithms
- Computing approximate Nash equilibria in network congestion games with polynomially decreasing cost functions
This page was built for publication: Improved approximation algorithms for directed Steiner forest
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q414883)
