Parameterized Single-Exponential Time Polynomial Space Algorithm for Steiner Tree

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)

zbMATH Keywords

recurrence relationSteiner treeFPT algorithm

Mathematics Subject Classification ID

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)

Structural parameterizations with modulator oblivion

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