Paper Info
Title
Fast Polynomial-Space Algorithms Using Möbius Inversion: Improving on Steiner Tree and Related Problems
Abstract
Given a graph with n vertices, k terminals and bounded integer weights on the edges, we compute the minimum Steiner Tree in ${\mathcal{O}^*}(2^k)$ time and polynomial space, where the ${\mathcal{O}^*}$ notation omits poly (n ,k ) factors. Among our results are also polynomial-space $\mathcal{O}^*(2^n)$ algorithms for several ${\mathcal{NP}}$-complete spanning tree and partition problems. The previous fastest known algorithms for these problems use the technique of dynamic programming among subsets, and require exponential space. We introduce the concept of branching walks and extend the Inclusion-Exclusion algorithm of Karp for counting Hamiltonian paths. Moreover, we show that our algorithms can also be obtained by applying Möbius inversion on the recurrences used for the dynamic programming algorithms.
Year
DOI
Venue
2009
10.1007/978-3-642-02927-1_59
ICALP
Keywords
Field
DocType
k terminal,n vertex,inclusion-exclusion algorithm,hamiltonian path,bounded integer weight,dynamic programming,fast polynomial-space,related problems,polynomial space,bius inversion,steiner tree,exponential space,dynamic programming algorithm,spanning tree
Integer,Discrete mathematics,Combinatorics,Vertex (geometry),Exact algorithm,Hamiltonian path,Steiner tree problem,Algorithm,PSPACE,Spanning tree,Mathematics,Bounded function
Conference
Volume
ISSN
Citations 
5555
0302-9743
51
PageRank 
References 
Authors
1.73
15
1
Name
Order
Citations
PageRank
Jesper Nederlof129424.22