activity
20192026
most citedAn Upper Bound on the Weisfeiler-Leman Dimension

1 citations · 1 across the 3 of their papers we have counts for

collaborators
Showing 2019 · cs.LOShow all

1 paper · 2 filters

cs.LO2019

Walk refinement, walk logic, and the iteration number of the Weisfeiler-Leman algorithm

Moritz Lichter, Ilia Ponomarenko, Pascal Schweitzer

We show that the 2-dimensional Weisfeiler-Leman algorithm stabilizes n-vertex graphs after at most O(n log n) iterations. This implies that if such graphs are distinguishable in 3-…