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

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 (6)

Extending the kernel for planar Steiner tree to the number of Steiner vertices ⋮ On the complexity of the cable-trench problem ⋮ Unnamed Item ⋮ Parameterized Complexity of Directed Steiner Tree on Sparse Graphs ⋮ Complexity of the Steiner Network Problem with Respect to the Number of Terminals ⋮ Approximate Counting of k-Paths: Deterministic and in Polynomial Space

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