14 citations · 40 across the 5 of their papers we have counts for
6 papers · 1 filter
On evaluation of permanents
Andreas Björklund, Thore Husfeldt, Petteri Kaski +1
We study the time and space complexity of matrix permanents over rings and semirings.
Counting Paths and Packings in Halves
Andreas Björklund, Thore Husfeldt, Petteri Kaski +1
It is shown that one can count -edge paths in an -vertex graph and -set -packings on an -element universe, respectively, in time and ${n \choose mk…
The fast intersection transform with applications to counting paths
Andreas Björklund, Thore Husfeldt, Petteri Kaski +1
We present an algorithm for evaluating a linear ``intersection transform'' of a function defined on the lattice of subsets of an -element set. In particular, the algorithm const…
Trimmed Moebius Inversion and Graphs of Bounded Degree
Andreas Björklund, Thore Husfeldt, Petteri Kaski +1
We study ways to expedite Yates's algorithm for computing the zeta and Moebius transforms of a function defined on the subset lattice. We develop a trimmed variant of Moebius inver…
Circumspect descent prevails in solving random constraint satisfaction problems
Mikko Alava, John Ardelius, Erik Aurell +4
We study the performance of stochastic local search algorithms for random instances of the -satisfiability (-SAT) problem. We introduce a new stochastic local search algorith…
Computing the Tutte polynomial in vertex-exponential time
Andreas Björklund, Thore Husfeldt, Petteri Kaski +1
The deletion--contraction algorithm is perhaps the most popular method for computing a host of fundamental graph invariants such as the chromatic, flow, and reliability polynomials…