15 citations · 87 across the 33 of their papers we have counts for
Showing 2013Show all
3 papers · 1 filter
cs.CC2013★ 1 cited
Parameterized (in)approximability of subset problems
Edouard Bonnet, Vangelis Th. Paschos
We discuss approximability and inapproximability in FPT-time for a large class of subset problems where a feasible solution is a subset of the input data and the value of i…
cs.CC2013
An exact algorithm for 1-in-3 SAT
Édouard Bonnet, Vangelis Th. Paschos
1-in-3 SAT is an NP-complete variant of 3-SAT\ where a "clause" is satisfied iff exactly one of its three literal is satisfied. We present here an exact algorithm solving \oit\ in…
cs.CC2013★ 3 cited
Multi-parameter complexity analysis for constrained size graph problems: using greediness for parameterization
Edouard Bonnet, Bruno Escoffier, Vangelis Th. Paschos +1
We study the parameterized complexity of a broad class of problems called "local graph partitioning problems" that includes the classical fixed cardinality problems as max k-vertex…