58 citations · 239 across the 47 of their papers we have counts for
4 papers · 1 filter
Computational Short Cuts in Infinite Domain Constraint Satisfaction
Peter Jonsson, Victor Lagerkvist, Sebastian Ordyniak
A backdoor in a finite-domain CSP instance is a set of variables where each possible instantiation moves the instance into a polynomial-time solvable class. Backdoors have found ma…
Almost Consistent Systems of Linear Equations
Konrad K. Dabrowski, Peter Jonsson, Sebastian Ordyniak +2
Checking whether a system of linear equations is consistent is a basic computational problem with ubiquitous applications. When dealing with inconsistent systems, one may seek an a…
SAT Backdoors: Depth Beats Size
Jan Dreier, Sebastian Ordyniak, Stefan Szeider
For several decades, much effort has been put into identifying classes of CNF formulas whose satisfiability can be decided in polynomial time. Classic results are the linear-time t…
An Algorithmic Framework for Locally Constrained Homomorphisms
Laurent Bulteau, Konrad K. Dabrowski, Noleen Köhler +2
A homomorphism from a guest graph to a host graph is locally bijective, injective or surjective if for every , the restriction of to the neighbourhood of…