Même, l'algorithme de retour en arrière limité d'Itai & Shamir pour 2-SAT: Est-ce vraiment linéaire?

Question

J'ai lu à Wikipedia (et à d'autres sources) sur l'algorithme de retour en arrière limité de même, Itai & Shamir pour résoudre le problème 2-autre à un moment linéaire, mais l'approche ne semble pas être linéaire, il n'y a pas de démonstration ni d'algorithme de mise en œuvre Pour le vérifier.

Voici la description de l'algorithme de Wikipedia: Même, Itai & Shamir - Backtracking limité.

Quelqu'un a-t-il entendu parler de cet algorithme? Quelqu'un a-t-il sa mise en œuvre / démonstration?

PS: Je ne cherche pas un algorithme pour résoudre le problème à 2 sites à un moment linéaire depuis que j'ai lu sur l'approche Aspvall, Plass & Tarjan. Je suis juste intéressé par l'ancien algorithme.