Parameterized Single-Exponential Time Polynomial Space Algorithm for Steiner Tree
From MaRDI portal
Publication:4619482
DOI10.1137/17M1140030zbMath1404.05208WikidataQ115525609 ScholiaQ115525609MaRDI QIDQ4619482
Fahad Panolan, Petteri Kaski, Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh
Publication date: 6 February 2019
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Nonnumerical algorithms (68W05) Graph algorithms (graph-theoretic aspects) (05C85) Connectivity (05C40) Signed and weighted graphs (05C22)
Related Items (1)
Cites Work
- Unnamed Item
- Unnamed Item
- Fundamentals of parameterized complexity
- Exact exponential algorithms.
- The Steiner problem with edge lengths 1 and 2
- A partial k-arboretum of graphs with bounded treewidth
- Fast polynomial-space algorithms using inclusion-exclusion. Improving on Steiner tree and related problems
- Computing optimal Steiner trees in polynomial space
- Sharp separation and applications to exact and parameterized algorithms
- Dynamic programming for minimum Steiner trees
- Parametrized complexity theory.
- Saving space by algebraization
- Subexponential-Time Parameterized Algorithm for Steiner Tree on Planar Graphs
- Fourier meets M\"{o}bius: fast subset convolution
- Fixed Parameter Tractability of Binary Near-Perfect Phylogenetic Tree Reconstruction
- Network Sparsification for Steiner Problems on Planar and Bounded-Genus Graphs
- Parameterized Algorithms to Preserve Connectivity
- Algorithms and Data Structures
- Steiner Tree Approximation via Iterative Randomized Rounding
- Parameterized Algorithms
- The steiner problem in graphs
This page was built for publication: Parameterized Single-Exponential Time Polynomial Space Algorithm for Steiner Tree
