Parameterized single-exponential time polynomial space algorithm for Steiner tree
DOI10.1137/17M1140030zbMATH Open1404.05208WikidataQ115525609 ScholiaQ115525609MaRDI QIDQ4619482FDOQ4619482
Authors: Fedor V. Fomin, Petteri Kaski, Daniel Lokshtanov, Fahad Panolan, Saket Saurabh 
Publication date: 6 February 2019
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Recommendations
- Parameterized single-exponential time polynomial space algorithm for Steiner tree
- Computing optimal Steiner trees in polynomial space
- Faster Steiner Tree Computation in Polynomial-Space
- Nearly ETH-tight Algorithms for Planar Steiner Tree with Terminals on Few Faces
- Nearly ETH-tight Algorithms for Planar Steiner Tree with Terminals on Few Faces
Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Nonnumerical algorithms (68W05) Signed and weighted graphs (05C22) Connectivity (05C40)
Cites Work
- Fundamentals of parameterized complexity
- Exact exponential algorithms.
- A partial k-arboretum of graphs with bounded treewidth
- Fast polynomial-space algorithms using inclusion-exclusion. Improving on Steiner tree and related problems
- Parametrized complexity theory.
- Steiner tree approximation via iterative randomized rounding
- Parameterized algorithms
- Title not available (Why is that?)
- Fourier meets M\"{o}bius: fast subset convolution
- Sharp separation and applications to exact and parameterized algorithms
- The steiner problem in graphs
- The Steiner problem with edge lengths 1 and 2
- Dynamic programming for minimum Steiner trees
- Subexponential-time parameterized algorithm for Steiner tree on planar graphs
- Saving space by algebraization
- Title not available (Why is that?)
- Computing optimal Steiner trees in polynomial space
- Algorithms and Data Structures
- Fixed Parameter Tractability of Binary Near-Perfect Phylogenetic Tree Reconstruction
- Parameterized algorithms to preserve connectivity
- Network sparsification for Steiner problems on planar and bounded-genus graphs
Cited In (5)
- Computing optimal Steiner trees in polynomial space
- Fast polynomial-space algorithms using inclusion-exclusion. Improving on Steiner tree and related problems
- Structural parameterizations with modulator oblivion
- Parameterized single-exponential time polynomial space algorithm for Steiner tree
- Faster Steiner Tree Computation in Polynomial-Space
This page was built for publication: Parameterized single-exponential time polynomial space algorithm for Steiner tree
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4619482)
