k-SAT

Created

Created

2023 Dec 5 6:11

Editor

Editor

Seonglae Cho

Creator

Creator

Seonglae Cho

Edited

Edited

2023 Dec 19 3:44

Refs

Refs

notion image

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.

2-SAT - Algorithms for Competitive Programming

https://cp-algorithms.com/graph/2SAT.html

Recommendations

/////