Parameterized Complexity of Directed Steiner Tree on Sparse Graphs
From MaRDI portal
Publication:5270408
DOI10.1137/15M103618XzbMath1371.68115OpenAlexW1578789027MaRDI QIDQ5270408
No author found.
Publication date: 23 June 2017
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/15m103618x
Steiner tree problemgraph algorithmsparameterized algorithmsalgorithms and data structuressparse graph classes
Analysis of algorithms and problem complexity (68Q25) Graph minors (05C83) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items
Approximation in (Poly-) logarithmic space, Tight Bounds for Planar Strongly Connected Steiner Subgraph with Fixed Number of Terminals (and Extensions), A relaxation of the directed disjoint paths problem: a global congestion metric helps, A Relaxation of the Directed Disjoint Paths Problem: A Global Congestion Metric Helps., Approximation in (Poly-) Logarithmic Space, Revising Johnson's table for the 21st century, Parameterized Approximation Schemes for Steiner Trees with Small Number of Steiner Vertices, Constant round distributed domination on graph classes with bounded expansion
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Fundamentals of parameterized complexity
- A series of approximation algorithms for the acyclic directed Steiner tree problem
- FPT algorithms for connected feedback vertex set
- Enumerate and expand: Improved algorithms for connected vertex cover and tree cover
- Approximation hardness of dominating set problems in bounded degree graphs
- Linear time algorithms for finding a dominating set of fixed size in degenerated graphs
- The Steiner problem with edge lengths 1 and 2
- The Steiner tree problem
- Proof of a conjecture of Mader, Erdős and Hajnal on topological complete subgraphs
- Approximation algorithms for connected dominating sets
- Diameter and treewidth in minor-closed graph families
- Which problems have strongly exponential complexity?
- Fixed parameter algorithms for DOMINATING SET and related problems on planar graphs
- Fast polynomial-space algorithms using inclusion-exclusion. Improving on Steiner tree and related problems
- Dynamic programming for minimum Steiner trees
- Parametrized complexity theory.
- Local tree-width, excluded minors, and approximation algorithms
- Parameterized Complexity of Directed Steiner Tree on Sparse Graphs
- Polynomial kernels for dominating set in graphs of bounded degeneracy and beyond
- Subexponential-Time Parameterized Algorithm for Steiner Tree on Planar Graphs
- Dominating Sets in Planar Graphs: Branch-Width and Exponential Speed-Up
- Parameterized Single-Exponential Time Polynomial Space Algorithm for Steiner Tree
- Subexponential parameterized algorithms on bounded-genus graphs and H -minor-free graphs
- Fourier meets M\"{o}bius: fast subset convolution
- Node-Weighted Steiner Tree and Group Steiner Tree in Planar Graphs
- The Rectilinear Steiner Tree Problem is $NP$-Complete
- Network Sparsification for Steiner Problems on Planar and Bounded-Genus Graphs
- A Nearly Best-Possible Approximation Algorithm for Node-Weighted Steiner Trees
- Topological cliques in graphs II
- Approximation Algorithms for Directed Steiner Problems
- Structure Theorem and Isomorphism Test for Graphs with Excluded Topological Subgraphs
- Integrality Ratio for Group Steiner Trees and Directed Steiner Trees
- Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
- Parameterized Algorithms
- The steiner problem in graphs
- Parameterized Complexity of Arc-Weighted Directed Steiner Problems
