Parameterized single-exponential time polynomial space algorithm for Steiner tree

DOI10.1137/17M1140030MaRDI QIDQ4619482zbMATH OpenWikidataFDO

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)

Copyright license Creative Commons Attribution 4.0 International

zbMATH Keywords

FPT algorithmrecurrence relationSteiner tree

Mathematics Subject Classification ID

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)

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

Cites work

• 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 partial k-arboretum of graphs with bounded treewidth
• Algorithms and Data Structures
• Computing optimal Steiner trees in polynomial space
• Dynamic programming for minimum Steiner trees
• Exact exponential algorithms.
• Fast polynomial-space algorithms using inclusion-exclusion. Improving on Steiner tree and related problems
• Fixed Parameter Tractability of Binary Near-Perfect Phylogenetic Tree Reconstruction
• Fourier meets M\"{o}bius: fast subset convolution
• Fundamentals of parameterized complexity
• Network sparsification for Steiner problems on planar and bounded-genus graphs
• Parameterized algorithms
• Parameterized algorithms to preserve connectivity
• Parametrized complexity theory.
• Saving space by algebraization
• Sharp separation and applications to exact and parameterized algorithms
• Steiner tree approximation via iterative randomized rounding
• Subexponential-time parameterized algorithm for Steiner tree on planar graphs
• The Steiner problem with edge lengths 1 and 2
• The steiner problem in graphs

Cited in

(5)

• Faster Steiner Tree Computation 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
• Computing optimal Steiner trees 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)