66 citations · 206 across the 36 of their papers we have counts for
Showing 2011 · cs.DSShow all
3 papers · 2 filters
cs.DS2011
k-Gap Interval Graphs
Fedor V. Fomin, Serge Gaspers, Petr Golovach +5
We initiate the study of a new parameterization of graph problems. In a multiple interval representation of a graph, each vertex is associated to at least one interval of the real…
cs.DS2011★ 6 cited
Backdoors to Satisfaction
Serge Gaspers, Stefan Szeider
A backdoor set is a set of variables of a propositional formula such that fixing the truth values of the variables in the backdoor set moves the formula into some polynomial-time d…
cs.DS2011★ 2 cited
Backdoors to Acyclic SAT
Serge Gaspers, Stefan Szeider
Backdoor sets, a notion introduced by Williams et al. in 2003, are certain sets of key variables of a CNF formula F that make it easy to solve the formula; by assigning truth value…