The paper mentions an algorithm published in 1980 is O( (n/log(n))^2 ), which is better than the Wagner-Fischer algorithm mentioned in the article, even if it's not strongly subquadratic.