Parameterized Approximation Algorithms for Bidirected Steiner Network Problems

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

zbMATH Keywords

planar graphsstrongly connected Steiner subgraphbidirected graphsdirected Steiner networkparameterized approximations

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

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