Parameterized complexity of directed Steiner tree on sparse graphs
From MaRDI portal
Recommendations
- Parameterized Complexity of Directed Steiner Tree on Sparse Graphs
- Parameterized complexity of arc-weighted directed Steiner problems
- The complexity landscape of fixed-parameter directed Steiner network problems
- Parameterized complexity of arc-weighted directed Steiner problems
- Parameterized Complexity of Directed Steiner Network with Respect to Shared Vertices and Arcs
Cites work
- scientific article; zbMATH DE number 4191148 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 1559541 (Why is no real title available?)
- scientific article; zbMATH DE number 750011 (Why is no real title available?)
- scientific article; zbMATH DE number 2119644 (Why is no real title available?)
- scientific article; zbMATH DE number 970831 (Why is no real title available?)
- scientific article; zbMATH DE number 2234775 (Why is no real title available?)
- A Nearly Best-Possible Approximation Algorithm for Node-Weighted Steiner Trees
- A series of approximation algorithms for the acyclic directed Steiner tree problem
- Approximation Algorithms for Directed Steiner Problems
- Approximation algorithms for connected dominating sets
- Approximation hardness of dominating set problems in bounded degree graphs
- Can you beat treewidth?
- Diameter and treewidth in minor-closed graph families
- Dominating Sets in Planar Graphs: Branch-Width and Exponential Speed-Up
- Dynamic programming for minimum Steiner trees
- Enumerate and expand: Improved algorithms for connected vertex cover and tree cover
- FPT algorithms for connected feedback vertex set
- Fast polynomial-space algorithms using inclusion-exclusion. Improving on Steiner tree and related problems
- Fixed parameter algorithms for DOMINATING SET and related problems on planar graphs
- Fourier meets M\"{o}bius: fast subset convolution
- Fundamentals of parameterized complexity
- Integrality Ratio for Group Steiner Trees and Directed Steiner Trees
- Linear time algorithms for finding a dominating set of fixed size in degenerated graphs
- Local tree-width, excluded minors, and approximation algorithms
- Network sparsification for Steiner problems on planar and bounded-genus graphs
- Node-Weighted Steiner Tree and Group Steiner Tree in Planar Graphs
- Parameterized Complexity of Directed Steiner Tree on Sparse Graphs
- Parameterized algorithms
- Parameterized complexity of arc-weighted directed Steiner problems
- Parameterized single-exponential time polynomial space algorithm for Steiner tree
- Parametrized complexity theory.
- Polynomial kernels for \textsc{Dominating Set} in graphs of bounded degeneracy and beyond
- Proof of a conjecture of Mader, Erdős and Hajnal on topological complete subgraphs
- Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
- Structure theorem and isomorphism test for graphs with excluded topological subgraphs
- Subexponential parameterized algorithms on bounded-genus graphs and H-minor-free graphs
- Subexponential-time parameterized algorithm for Steiner tree on planar graphs
- The Rectilinear Steiner Tree Problem is NP-Complete
- The Steiner problem with edge lengths 1 and 2
- The Steiner tree problem
- The steiner problem in graphs
- Topological cliques in graphs II
- Which problems have strongly exponential complexity?
Cited in
(17)- Approximation in (poly-) logarithmic space
- A Relaxation of the Directed Disjoint Paths Problem: A Global Congestion Metric Helps.
- New Parameterized Algorithms for APSP in Directed Graphs
- Parameterized complexity of arc-weighted directed Steiner problems
- Parameterized Complexity of Directed Steiner Tree on Sparse Graphs
- Parameterized Complexity of Directed Steiner Network with Respect to Shared Vertices and Arcs
- Complexity of the directed spanning cactus problem
- Parameterized approximation schemes for Steiner trees with small number of Steiner vertices
- Distributed domination on sparse graph classes
- Approximation in (Poly-) Logarithmic Space
- A relaxation of the directed disjoint paths problem: a global congestion metric helps
- Parameterised distance to local irregularity
- Tight bounds for planar strongly connected Steiner subgraph with fixed number of terminals (and extensions)
- The complexity landscape of fixed-parameter directed Steiner network problems
- Parameterised distance to local irregularity
- Revising Johnson's table for the 21st century
- Constant round distributed domination on graph classes with bounded expansion
This page was built for publication: Parameterized complexity of directed Steiner tree on sparse graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5270408)
