89 citations · 138 across the 17 of their papers we have counts for
Showing 2021Show all
2 papers · 1 filter
cs.DS2021★ 1 cited
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…
cs.CC2021
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…