Currently displaying 1 – 1 of 1

Showing per page

Order by Relevance | Title | Year of publication

Satisfiability and matchings in bipartite graphs: relationship and tractability.

Belaid Benhamou — 2004

RACSAM

Satisfiability problem is the task to establish either a given CNF logical formula admits a model or not. It is known to be the canonical NP-complete problem. We study in this note the relationship between matchings in bipartite graphs and the satisfiability problem, and prove that some restrictions of formulae including the known r-r-SAT class are trivially satisfiable. We present an algorithm which finds a model for such formulas in polynomial time complexity if one exists or, failing this, proves...

Page 1

Download Results (CSV)