89 citations · 138 across the 17 of their papers we have counts for
20 papers
Counting equitable -colorings in graphs of bounded clique-width
Holger Dell, Thore Husfeldt, Amir Nikabadi
For a graph , a proper -coloring of is \emph{equitable} if the sizes of any two color classes differ by at most one. The \textsc{Equitable -Coloring} problem asks, for…
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…
Modular counting of subgraphs: Matchings, matching-splittable graphs, and paths
Radu Curticapean, Holger Dell, Thore Husfeldt
We systematically investigate the complexity of counting subgraph patterns modulo fixed integers. For example, it is known that the parity of the number of -matchings can be det…
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…