most citedUpper Bounds on the Quantifier Depth for Graph Differentiation in First-Order Logic

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

collaborators

1 paper

cs.LO2016★ 2 cited

Upper Bounds on the Quantifier Depth for Graph Differentiation in First-Order Logic

Sandra Kiefer, Pascal Schweitzer

We show that on graphs with n vertices, the 2-dimensional Weisfeiler-Leman algorithm requires at most O(n^2/log(n)) iterations to reach stabilization. This in particular shows that…