375 citations · 494 across the 29 of their papers we have counts for
5 papers · 1 filter
Shortest reconfiguration paths in the solution space of Boolean formulas
Amer E. Mouawad, Naomi Nishimura, Vinayak Pathak +1
Given a Boolean formula and a satisfying assignment, a flip is an operation that changes the value of a variable in the assignment so that the resulting assignment remains satisfyi…
Reconfiguration over tree decompositions
Amer E. Mouawad, Naomi Nishimura, Venkatesh Raman +1
A vertex-subset graph problem defines which subsets of the vertices of an input graph are feasible solutions. The reconfiguration version of a vertex-subset problem asks wh…
Vertex Cover Reconfiguration and Beyond
Amer E. Mouawad, Naomi Nishimura, Venkatesh Raman +1
In the Vertex Cover Reconfiguration (VCR) problem, given a graph , positive integers and and two vertex covers and of of size at most , we determine wh…
On the Parameterized Complexity of Reconfiguration Problems
Amer E. Mouawad, Naomi Nishimura, Venkatesh Raman +2
We present the first results on the parameterized complexity of reconfiguration problems, where a reconfiguration version of an optimization problem takes as input two feasible…
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…