# Satisfiability and matchings in bipartite graphs: relationship and tractability.

RACSAM (2004)

- Volume: 98, Issue: 1, page 55-63
- ISSN: 1578-7303

## Access Full Article

top## Abstract

top## How to cite

topBenhamou, Belaid. "Satisfiability and matchings in bipartite graphs: relationship and tractability.." RACSAM 98.1 (2004): 55-63. <http://eudml.org/doc/41035>.

@article{Benhamou2004,

abstract = {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-SAT1 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 in polynomial time complexity that the current formula is not an element of the restricted class.},

author = {Benhamou, Belaid},

journal = {RACSAM},

keywords = {CNF logical formula},

language = {eng},

number = {1},

pages = {55-63},

title = {Satisfiability and matchings in bipartite graphs: relationship and tractability.},

url = {http://eudml.org/doc/41035},

volume = {98},

year = {2004},

}

TY - JOUR

AU - Benhamou, Belaid

TI - Satisfiability and matchings in bipartite graphs: relationship and tractability.

JO - RACSAM

PY - 2004

VL - 98

IS - 1

SP - 55

EP - 63

AB - 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-SAT1 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 in polynomial time complexity that the current formula is not an element of the restricted class.

LA - eng

KW - CNF logical formula

UR - http://eudml.org/doc/41035

ER -

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.