**Definition:**

(x1 v x2) ^ (x1 v -x2) ^ ....

per clause two literals.

**Algorithm to found whether there exits a possible assignment or not?**

Build implication graph corresponding and then check whether there exists a path from x to -x or not.

If such path exists, then no valid assignment can be done.

Building implication graph

(x v y) add edge -x to y, and -y to x.

**Algorithm to find a possible assignment?**

First check for the existence case.

for each unassigned literal x, assign it to true and all the y such x -> y, then assign y to true,

Assign all the opposite of these literals to be false.

**Implementation:**

**Problems to practice:**

https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=43&page=show_problem&problem=2453

http://www.spoj.com/problems/TORNJEVI/

http://www.spoj.com/problems/SUPSUP/

http://2011.nwerc.eu/results.php (Piece it Together ).

http://2012.nwerc.eu/en/results/problems/

**References:**

http://users.cms.caltech.edu/~umans/cs21/lec17.pdf

http://kartikkukreja.wordpress.com/2013/05/16/solving-2-sat-in-linear-time/

http://classes.soe.ucsc.edu/cmps132/Winter05/hw/hw8sols.pdf

http://apps.topcoder.com/forums/?module=Thread&threadID=803822&start=0&mc=2

## No comments:

## Post a Comment