The fast intersection transform with applications to counting paths
作者： Thore Husfeldt , Mikko Koivisto , Petteri Kaski , Andreas Björklund
DOI:
关键词:
摘要: We present an algorithm for evaluating a linear ``intersection transform'' of function defined on the lattice subsets $n$-element set. In particular, constructs arithmetic circuit transform in ``down-closure time'' relative to support and evaluation domain. As application, we develop that, given as input digraph with $n$ vertices bounded integer weights at edges, counts paths by weight length $0\leq\ell\leq n-1$ time $O^*(\exp(n\cdot H(\ell/(2n))))$, where $H(p)=-p\log p-(1-p)\log(1-p)$, notation $O^*(\cdot)$ suppresses factor polynomial $n$.
arxiv.org
harvard.edu参考文章(25)
Andreas Björklund, Thore Husfeldt, Petteri Kaski, Mikko Koivisto, Fourier meets möbius: fast subset convolution Proceedings of the thirty-ninth annual ACM symposium on Theory of computing - STOC '07. pp. 67- 74 ,(2007) , 10.1145/1250790.1250801
James W. Cooley, John W. Tukey, An algorithm for the machine calculation of complex Fourier series Mathematics of Computation. ,vol. 19, pp. 297- 301 ,(1965) , 10.1090/S0025-5718-1965-0178586-1
Richard Bellman, COMBINATORIAL PROCESSES AND DYNAMIC PROGRAMMING ,(1958)
Andreas Björklund, Thore Husfeldt, Petteri Kaski, Mikko Koivisto, Trimmed Moebius Inversion and Graphs of Bounded Degree symposium on theoretical aspects of computer science. ,vol. 47, pp. 637- 654 ,(2010) , 10.1007/S00224-009-9185-7
Noga Alon, Raphael Yuster, Uri Zwick, Color-coding Journal of the ACM. ,vol. 42, pp. 844- 856 ,(1995) , 10.1145/210332.210337
Heidi Gebauer, On the number of hamilton cycles in bounded degree graphs analytic algorithmics and combinatorics. pp. 241- 248 ,(2008)
D.B. Shmoys, E.L. Lawler, Jan Karel Lenstra, A.H.G. Rinnooy Kan, The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization ,(1985)
David Eppstein, The Traveling Salesman Problem for Cubic Graphs Journal of Graph Algorithms and Applications. ,vol. 11, pp. 61- 81 ,(2007) , 10.7155/JGAA.00137
Ryan Williams, Finding paths of length k in O*(2^k) time arXiv: Data Structures and Algorithms. ,(2008)
Jan Karel Lenstra, David Shmoys, The Traveling Salesman Problem: A Computational Study ,(2007)