14 citations · 32 across the 4 of their papers we have counts for
4 papers
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…
Solving connectivity problems parameterized by treewidth in single exponential time
Marek Cygan, Jesper Nederlof, Marcin Pilipczuk +3
For the vast majority of local graph problems standard dynamic programming techniques give c^tw V^O(1) algorithms, where tw is the treewidth of the input graph. On the other hand,…