The fast intersection transform with applications to counting paths
| dc.creator | Björklund, Andreas | |
| dc.creator | Husfeldt, Thore | |
| dc.creator | Kaski, Petteri | |
| dc.creator | Koivisto, Mikko | |
| dc.date | 2008-09-15 | |
| dc.date.accessioned | 2026-07-07T10:02:50Z | |
| dc.date.available | 2026-07-07T10:02:50Z | |
| dc.description | We present an algorithm for evaluating a linear ``intersection transform'' of a function defined on the lattice of subsets of an $n$-element set. In particular, the algorithm constructs an arithmetic circuit for evaluating the transform in ``down-closure time'' relative to the support of the function and the evaluation domain. As an application, we develop an algorithm that, given as input a digraph with $n$ vertices and bounded integer weights at the edges, counts paths by weight and given length $0\leq\ell\leq n-1$ in time $O^*(\exp(n\cdot H(\ell/(2n))))$, where $H(p)=-p\log p-(1-p)\log(1-p)$, and the notation $O^*(\cdot)$ suppresses a factor polynomial in $n$. | |
| dc.description | 11 pages | |
| dc.identifier | https://arxiv.org/abs/0809.2489 | |
| dc.identifier | http://arxiv.org/abs/0809.2489 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/169112 | |
| dc.subject | Data Structures and Algorithms | |
| dc.subject | Discrete Mathematics | |
| dc.title | The fast intersection transform with applications to counting paths | |
| dc.type | text |