Parameterized Approximation Algorithms for Bidirected Steiner Network Problems
From MaRDI portal
Publication:5009577
DOI10.4230/LIPIcs.ESA.2018.20OpenAlexW2963340170MaRDI QIDQ5009577
Rajesh Chitnis, Andreas Emil Feldmann, Pasin Manurangsi
Publication date: 4 August 2021
Full work available at URL: https://arxiv.org/abs/1707.06499
planar graphsstrongly connected Steiner subgraphbidirected graphsdirected Steiner networkparameterized approximations
Related Items (5)
A tight lower bound for planar Steiner orientation ⋮ Tight Bounds for Planar Strongly Connected Steiner Subgraph with Fixed Number of Terminals (and Extensions) ⋮ Complexity of the Steiner Network Problem with Respect to the Number of Terminals ⋮ Parameterized Approximation Schemes for Steiner Trees with Small Number of Steiner Vertices ⋮ To close is easier than to open: dual parameterization to \(k\)-median
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Improved approximation algorithms for directed Steiner forest
- On approximate optimal dual power assignment for biconnectivity and edge-biconnectivity
- New approximation algorithms for the Steiner tree problems
- Which problems have strongly exponential complexity?
- Approximation algorithms for spanner problems and directed Steiner forest
- Dual power assignment optimization and fault tolerance in WSNs
- An 11/6-approximation algorithm for the network Steiner problem
- Design networks with bounded pairwise distance
- Solving Planar k -Terminal Cut in $O(n^{c \sqrt{k}})$ Time
- A Tight Lower Bound for Planar Multiway Cut with Fixed Number of Terminals
- Fixed-Parameter and Approximation Algorithms: A New Look
- Subexponential-Time Parameterized Algorithm for Steiner Tree on Planar Graphs
- Set connectivity problems in undirected graphs and the directed steiner network problem
- Lossy Kernels for Connected Dominating Set on Sparse Graphs
- The Directed Steiner Network Problem is Tractable for a Constant Number of Terminals
- Fixed Parameter Approximations for k-Center Problems in Low Highway Dimension Graphs
- Optimal Parameterized Algorithms for Planar Facility Location Problems Using Voronoi Diagrams
- Polylogarithmic inapproximability
- Approximation Algorithms for Several Graph Augmentation Problems
- A New Approximation Algorithm for the Steiner Tree Problem with Performance Ratio 5/3
- Network Sparsification for Steiner Problems on Planar and Bounded-Genus Graphs
- The Constant Inapproximability of the Parameterized Dominating Set Problem
- Lossy Kernels for Graph Contraction Problems
- When Trees Collide: An Approximation Algorithm for the Generalized Steiner Problem on Networks
- Lossy kernelization
- ETH-Hardness of Approximating 2-CSPs and Directed Steiner Network
- A (1+epsilon)-Approximation for Unsplittable Flow on a Path in Fixed-Parameter Running Time
- Subexponential parameterized algorithms for graphs of polynomial growth
- From Gap-Exponential Time Hypothesis to Fixed Parameter Tractable Inapproximability: Clique, Dominating Set, and More
- Parameterized Approximation Schemes Using Graph Widths
- Excluded minors, network decomposition, and multicommodity flow
- Tighter Bounds for Graph Steiner Tree Approximation
- Design of Survivable Networks: A survey
- Tight Bounds for Planar Strongly Connected Steiner Subgraph with Fixed Number of Terminals (and Extensions)
- A subexponential parameterized algorithm for Subset TSP on planar graphs
- Improved algorithms for min cut and max flow in undirected planar graphs
- A Faster Algorithm for the Steiner Tree Problem
- Parameterized Algorithms
- Steiner Minimal Trees
- The steiner problem in graphs
- Parameterized Complexity of Arc-Weighted Directed Steiner Problems
- On the complexity of \(k\)-SAT
This page was built for publication: Parameterized Approximation Algorithms for Bidirected Steiner Network Problems
