121 citations · 181 across the 38 of their papers we have counts for
4 papers · 1 filter
Fast Hamiltonicity checking via bases of perfect matchings
Marek Cygan, Stefan Kratsch, Jesper Nederlof
For an even integer t \geq 2, the Matchings Connecivity matrix H_t is a matrix that has rows and columns both labeled by all perfect matchings of the complete graph K_t on t vertic…
Solving weighted and counting variants of connectivity problems parameterized by treewidth deterministically in single exponential time
Hans L. Bodlaender, Marek Cygan, Stefan Kratsch +1
It is well known that many local graph problems, like Vertex Cover and Dominating Set, can be solved in 2^{O(tw)}|V|^{O(1)} time for graphs G=(V,E) with a given tree decomposition…
Reducing a Target Interval to a Few Exact Queries
Jesper Nederlof, Erik Jan van Leeuwen, Ruben van der Zwaan
Many combinatorial problems involving weights can be formulated as a so-called ranged problem. That is, their input consists of a universe , a (succinctly-represented) set famil…
Homomorphic Hashing for Sparse Coefficient Extraction
Petteri Kaski, Mikko Koivisto, Jesper Nederlof
We study classes of Dynamic Programming (DP) algorithms which, due to their algebraic definitions, are closely related to coefficient extraction methods. DP algorithms can easily b…