Satisfiability and matchings in bipartite graphs: relationship and tractability.

Belaid Benhamou

RACSAM (2004)

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

Abstract

top
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.

How to cite

top

Benhamou, 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 ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.