Parameterized approximation algorithms for bidirected Steiner network problems
From MaRDI portal
Publication:5009577
Recommendations
- Tight bounds for planar strongly connected Steiner subgraph with fixed number of terminals (and extensions)
- Tight bounds for planar strongly connected Steiner subgraph with fixed number of terminals (and extensions)
- The Directed Steiner Network Problem is Tractable for a Constant Number of Terminals
- Parameterized complexity of arc-weighted directed Steiner problems
- The complexity landscape of fixed-parameter directed Steiner network problems
Cites work
- A (1+)-approximation for unsplittable flow on a path in fixed-parameter running time
- A birthday repetition theorem and complexity of approximating dense CSPs
- A Faster Algorithm for the Steiner Tree Problem
- A New Approximation Algorithm for the Steiner Tree Problem with Performance Ratio 5/3
- A subexponential parameterized algorithm for subset TSP on planar graphs
- A tight lower bound for planar multiway cut with fixed number of terminals
- An 11/6-approximation algorithm for the network Steiner problem
- Approximation Algorithms for Several Graph Augmentation Problems
- Approximation algorithms for spanner problems and directed Steiner forest
- Design networks with bounded pairwise distance
- Design of Survivable Networks: A survey
- Dual power assignment optimization and fault tolerance in WSNs
- ETH-hardness of approximating 2-CSPs and directed Steiner network
- Excluded minors, network decomposition, and multicommodity flow
- Fixed parameter approximations for \(k\)-center problems in low highway dimension graphs
- Fixed-Parameter and Approximation Algorithms: A New Look
- From gap-exponential time hypothesis to fixed parameter tractable inapproximability: clique, dominating set, and more
- Improved algorithms for \textsc{Min-cut} and \textsc{Max-flow} in undirected planar graphs
- Improved approximation algorithms for directed Steiner forest
- Lossy kernelization
- Lossy kernels for connected dominating set on sparse graphs
- Lossy kernels for graph contraction problems
- Network sparsification for Steiner problems on planar and bounded-genus graphs
- New approximation algorithms for the Steiner tree problems
- On approximate optimal dual power assignment for biconnectivity and edge-biconnectivity
- On the complexity of k-SAT
- Parameterized algorithms
- Parameterized approximation schemes for Steiner trees with small number of Steiner vertices
- Parameterized Approximation Schemes Using Graph Widths
- Parameterized complexity of arc-weighted directed Steiner problems
- Polylogarithmic inapproximability
- Set connectivity problems in undirected graphs and the directed Steiner network problem
- Solving Planar k -Terminal Cut in $O(n^{c \sqrt{k}})$ Time
- Steiner Minimal Trees
- Subexponential parameterized algorithms for graphs of polynomial growth
- Subexponential parameterized odd cycle transversal on planar graphs
- Subexponential-time parameterized algorithm for Steiner tree on planar graphs
- The constant inapproximability of the parameterized dominating set problem
- The Directed Steiner Network Problem is Tractable for a Constant Number of Terminals
- The steiner problem in graphs
- Tight bounds for planar strongly connected Steiner subgraph with fixed number of terminals (and extensions)
- Tighter Bounds for Graph Steiner Tree Approximation
- When Trees Collide: An Approximation Algorithm for the Generalized Steiner Problem on Networks
- Which problems have strongly exponential complexity?
Cited in
(14)- A tight lower bound for planar Steiner orientation
- To close is easier than to open: dual parameterization to \(k\)-median
- scientific article; zbMATH DE number 1305468 (Why is no real title available?)
- Parameterized Approximation Algorithms for Bidirected Steiner Network Problems
- Complexity of the Steiner Network Problem with Respect to the Number of Terminals
- Tight bounds for planar strongly connected Steiner subgraph with fixed number of terminals (and extensions)
- A tight algorithm for strongly connected Steiner subgraph on two terminals with demands
- Tight bounds for planar strongly connected Steiner subgraph with fixed number of terminals (and extensions)
- Parameterized Complexity of Directed Steiner Network with Respect to Shared Vertices and Arcs
- Parameterized approximation schemes for Steiner trees with small number of Steiner vertices
- Parameterized inapproximability for Steiner orientation by gap amplification
- Subexponential parameterized directed Steiner network problems on planar graphs: a complete classification
- The complexity landscape of fixed-parameter directed Steiner network problems
- The strongish planted clique hypothesis and its consequences
This page was built for publication: Parameterized approximation algorithms for bidirected Steiner network problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5009577)
