Counting Paths and Packings in Halves
| dc.creator | Björklund, Andreas | |
| dc.creator | Husfeldt, Thore | |
| dc.creator | Kaski, Petteri | |
| dc.creator | Koivisto, Mikko | |
| dc.date | 2009-04-20 | |
| dc.date.accessioned | 2026-07-07T13:06:23Z | |
| dc.date.available | 2026-07-07T13:06:23Z | |
| dc.description | It is shown that one can count $k$-edge paths in an $n$-vertex graph and $m$-set $k$-packings on an $n$-element universe, respectively, in time ${n \choose k/2}$ and ${n \choose mk/2}$, up to a factor polynomial in $n$, $k$, and $m$; in polynomial space, the bounds hold if multiplied by $3^{k/2}$ or $5^{mk/2}$, respectively. These are implications of a more general result: given two set families on an $n$-element universe, one can count the disjoint pairs of sets in the Cartesian product of the two families with $\nO(n \ell)$ basic operations, where $\ell$ is the number of members in the two families and their subsets. | |
| dc.identifier | https://arxiv.org/abs/0904.3093 | |
| dc.identifier | http://arxiv.org/abs/0904.3093 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/227765 | |
| dc.subject | Data Structures and Algorithms | |
| dc.subject | Discrete Mathematics | |
| dc.title | Counting Paths and Packings in Halves | |
| dc.type | text |