5 papers
An Exact Algorithm for finding Maximum Induced Matching in Subcubic Graphs
Gordon Hoi, Ammar Fathin Sabili, Frank Stephan
The Maximum Induced Matching problem asks to find the maximum such that, given a graph , can we find a subset of vertices of size for which every vertices …
Improved Algorithms for the General Exact Satisfiability Problem
Gordon Hoi, Frank Stephan
The Exact Satisfiability problem asks if we can find a satisfying assignment to each clause such that exactly one literal in each clause is assigned , while the rest are all ass…
An Improved Exact Algorithm for the Exact Satisfiability Problem
Gordon Hoi
The Exact Satisfiability problem, XSAT, is defined as the problem of finding a satisfying assignment to a formula in CNF such that exactly one literal in each clause is assigne…
A Faster Exact Algorithm to Count X3SAT Solutions
Gordon Hoi, Sanjay Jain, Frank Stephan
The Exact Satisfiability problem, XSAT, is defined as the problem of finding a satisfying assignment to a formula in CNF such that there is exactly one literal in each clause assig…
A Fast Exponential Time Algorithm for Max Hamming Distance X3SAT
Gordon Hoi, Sanjay Jain, Frank Stephan
X3SAT is the problem of whether one can satisfy a given set of clauses with up to three literals such that in every clause, exactly one literal is true and the others are false. A…