121 citations · 360 across the 111 of their papers we have counts for
4 papers · 1 filter
On Problems as Hard as CNFSAT
Marek Cygan, Holger Dell, Daniel Lokshtanov +6
The field of exact exponential time algorithms for NP-hard problems has thrived over the last decade. While exhaustive search remains asymptotically the fastest known algorithm for…
Parameterized Complexity of MaxSat Above Average
Robert Crowston, Gregory Gutin, Mark Jones +2
In MaxSat, we are given a CNF formula with variables and clauses and asked to find a truth assignment satisfying the maximum number of clauses. Let be th…
Bidimensionality and Geometric Graphs
Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh
In this paper we use several of the key ideas from Bidimensionality to give a new generic approach to design EPTASs and subexponential time parameterized algorithms for problems on…
Hitting and Harvesting Pumpkins
Gwenaël Joret, Christophe Paul, Ignasi Sau +2
The "c-pumpkin" is the graph with two vertices linked by c>0 parallel edges. A c-pumpkin-model in a graph G is a pair A,B of disjoint subsets of vertices of G, each inducing a conn…