21 citations · 91 across the 19 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…
LP Rounding for k-Centers with Non-uniform Hard Capacities
Marek Cygan, MohammadTaghi Hajiaghayi, Samir Khuller
In this paper we consider a generalization of the classical k-center problem with capacities. Our goal is to select k centers in a graph, and assign each node to a nearby center, s…
On fixed-parameter algorithms for Split Vertex Deletion
Marek Cygan, Marcin Pilipczuk
In the Split Vertex Deletion problem, given a graph G and an integer k, we ask whether one can delete k vertices from the graph G to obtain a split graph (i.e., a graph, whose vert…