5 citations · 7 across the 24 of their papers we have counts for
Showing 2017Show all
2 papers · 1 filter
cs.CC2017
Kernelization of Constraint Satisfaction Problems: A Study through Universal Algebra
Victor Lagerkvist, Magnus Wahlström
A kernelization algorithm for a computational problem is a procedure which compresses an instance into an equivalent instance whose size is bounded with respect to a complexity par…
cs.CC2017★ 5 cited
Time Complexity of Constraint Satisfaction via Universal Algebra
Peter Jonsson, Victor Lagerkvist, Biman Roy
The exponential-time hypothesis (ETH) states that 3-SAT is not solvable in subexponential time, i.e. not solvable in O(c^n) time for arbitrary c > 1, where n denotes the number of…