Parameterized Single-Exponential Time Polynomial Space Algorithm for Steiner Tree

2015/01/01 by Fedor V. Fomin, Petteri Kaski, Daniel Lokshtanov +2 · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Algorithm #Combinatorics #Complexity and Algorithms in Graphs #Computer science #Discrete mathematics #Exponential function #Graph #Interconnection Networks and Systems #Mathematical analysis #Mathematics #Parameterized complexity #Running time #Space (punctuation) #Steiner tree problem #Time complexity #Tree (set theory) #Vertex (graph theory)

paper · doi:10.1007/978-3-662-47672-7_40

crossref issued 2015/01/01 · crossref published 2015/01/01 · crossref published-print 2015/01/01 · openalex publication_date 2015/01/01 · crossref created 2015/06/19 · crossref published-online 2015/06/20 · crossref deposited 2023/02/21 · crossref indexed 2025/03/27 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/04

Citations

• Steiner Tree Approximation via Iterative Randomized Rounding
• The steiner problem in graphs
• Dynamic Programming for Minimum Steiner Trees
• Fourier meets möbius: fast subset convolution
• Saving space by algebraization
• A partial k-arboretum of graphs with bounded treewidth
• A Remark on Stirling's Formula

Cited by

• Steiner tree problem [wikipedia]