Parameterized Single-Exponential Time Polynomial Space Algorithm for Steiner Tree
DOI10.1007/978-3-662-47672-7_40zbMath1433.05299OpenAlexW1190319202WikidataQ60488396 ScholiaQ60488396MaRDI QIDQ3448810
Saket Saurabh, Fahad Panolan, Fedor V. Fomin, Daniel Lokshtanov, Petteri Kaski
Publication date: 27 October 2015
Published in: Automata, Languages, and Programming (Search for Journal in Brave)
Full work available at URL: https://aaltodoc.aalto.fi/handle/123456789/23026
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 (6)
Cites Work
- Unnamed Item
- Fundamentals of parameterized complexity
- 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
- Dynamic programming for minimum Steiner trees
- Saving space by algebraization
- Subexponential-Time Parameterized Algorithm for Steiner Tree on Planar Graphs
- A Remark on Stirling's Formula
- 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
- The steiner problem in graphs
This page was built for publication: Parameterized Single-Exponential Time Polynomial Space Algorithm for Steiner Tree