I have read in Wikipedia (and other sources) about the "
Even, Itai & Shamir Limited backtracking" algorithm for solving 2-SAT problem in a linear time, but the approach doesn't seem to be linear, there is no demonstration nor algorithm implementation to check it.
Here is the algorithm description from Wikipedia Even, Itai & Shamir - Limited backtracking.
Has anyone heard about this algorithm? Does anyone have its implementation/demonstration?
PS: I am not searching for an algorithm to solve 2-SAT problem in a linear time since I have read about
Aspvall, Plass & Tarjan approach. I am just interested in the former algorithm.
Thanks in advance.