Anche, algoritmo di backtracking limitato di Itai e Shamir per 2-Sat: è davvero lineare?

Question

Ho letto in Wikipedia (e altre fonti) sull'algoritmo di backtracking limitato di pari, Itai e Shamir per risolvere il problema a 2 sa-sat in un tempo lineare, ma l'approccio non sembra essere lineare, non c'è dimostrazione né implementazione dell'algoritmo per controllarlo.

Ecco la descrizione dell'algoritmo di Wikipedia: Anche, Itai e Shamir - limitato backtracking.

Qualcuno ha sentito parlare di questo algoritmo? Qualcuno ha la sua implementazione/dimostrazione?

PS: non sto cercando un algoritmo per risolvere il problema a 2 sa-sat in un tempo lineare da quando ho letto dell'approccio Aspvall, Plass & Tarjan. Sono solo interessato all'ex algoritmo.