89 citations · 138 across the 17 of their papers we have counts for
16 papers · 1 filter
Finding longer cycles via shortest colourful cycle
Andreas Björklund, Thore Husfeldt
We consider the parameterised -Long Cycle problem, in which you are given an -vertex undirected graph , a specified edge in , and a positive integer , and are…
Fast Deterministic Chromatic Number under the Asymptotic Rank Conjecture
Andreas Björklund, Radu Curticapean, Thore Husfeldt +2
In this paper we further explore the recently discovered connection by Björklund and Kaski [STOC 2024] and Pratt [STOC 2024] between the asymptotic rank conjecture of Strassen [Pro…
The Shortest Even Cycle Problem is Tractable
Andreas Björklund, Thore Husfeldt, Petteri Kaski
Given a directed graph, we show how to efficiently find a shortest (directed, simple) cycle on an even number of vertices. As far as we know, no polynomial-time algorithm was previ…
Counting Shortest Two Disjoint Paths in Cubic Planar Graphs with an NC Algorithm
Andreas Björklund, Thore Husfeldt
Given an undirected graph and two disjoint vertex pairs and , the Shortest two disjoint paths problem (S2DP) asks for the minimum total length of two vertex disj…
Multivariate Analysis of Orthogonal Range Searching and Graph Distances Parameterized by Treewidth
Karl Bringmann, Thore Husfeldt, Måns Magnusson
We show that the eccentricities, diameter, radius, and Wiener index of an undirected -vertex graph with nonnegative edge lengths can be computed in time $O(n\cdot \binom{k+\lcei…
Extensor-Coding
Cornelius Brand, Holger Dell, Thore Husfeldt
We devise an algorithm that approximately computes the number of paths of length in a given directed graph with vertices up to a multiplicative error of …
Graph colouring algorithms
Thore Husfeldt
This chapter presents an introduction to graph colouring algorithms. The focus is on vertex-colouring algorithms that work for general classes of graphs with worst-case performance…
The Parity of Directed Hamiltonian Cycles
Andreas Björklund, Thore Husfeldt
We present a deterministic algorithm that given any directed graph on n vertices computes the parity of its number of Hamiltonian cycles in O(1.619^n) time and polynomial space. Fo…
Invitation to Algorithmic Uses of Inclusion-Exclusion
Thore Husfeldt
I give an introduction to algorithmic uses of the principle of inclusion-exclusion. The presentation is intended to be be concrete and accessible, at the expense of generality and…
Narrow sieves for parameterized paths and packings
Andreas Björklund, Thore Husfeldt, Petteri Kaski +1
We present randomized algorithms for some well-studied, hard combinatorial problems: the k-path problem, the p-packing of q-sets problem, and the q-dimensional p-matching problem.…
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…
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…
Fourier meets Möbius: fast subset convolution
Andreas Björklund, Thore Husfeldt, Petteri Kaski +1
We present a fast algorithm for the subset convolution problem: given functions f and g defined on the lattice of subsets of an n-element set N, compute their subset convolution f*…