Seonglae Cho
2-SAT
Given a graph G=(V,E) and two vertices s,t in V, finding if there is a path from s to t in G is polynomial-time decidable
- Vertex for each variable and a negation of a variable
- Edge (a,b) iff there exists a clause equivalent to (¬ab)
2-SAT example
2-SAT - Algorithms for Competitive Programming
The goal of this project is to translate the wonderful resource http://e-maxx.ru/algo which provides descriptions of many algorithms and data structures especially popular in field of competitive programming. Moreover we want to improve the collected knowledge by extending the articles and adding new articles to the collection.
https://cp-algorithms.com/graph/2SAT.html