The Classical Weisfeiler-Leman Algorithm Stabilizes in $O(n)$ Rounds

Simon Döring, Daniel Neuen

The classical Weisfeiler-Leman algorithm (also known as the $2$-dimensional Weisfeiler-Leman algorithm) is a simple combinatorial algorithm that was originally designed as a heuris…