Even, Itai & Shamir Limited backtrackiçng algorithm for 2-SAT (is it really linear)

0 votes
asked Sep 11, 2017 by younes-zeboudj

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.

Your answer

Your name to display (optional):
Privacy: Your email address will only be used for sending these notifications.
Anti-spam verification:
To avoid this verification in future, please log in or register.
Welcome to Q&A, where you can ask questions and receive answers from other members of the community.
Website Online Counter

...