1 citations · 1 across the 3 of their papers we have counts for
5 papers
Isomorphism of tournaments with bounded VC dimension
Simon Raßmann, Pascal Schweitzer
The tournament isomorphism problem is one of the two fundamental bottlenecks to designing better algorithms for the graph isomorphism problem. Though the problem has been investiga…
Finite Variable Counting Logics with Restricted Requantification
Simon Raßmann, Georg Schindling, Pascal Schweitzer
Counting logics with a bounded number of variables form one of the central concepts in descriptive complexity theory. Although they restrict the number of variables that a formula…
An Upper Bound on the Weisfeiler-Leman Dimension
Thomas Schneider, Pascal Schweitzer
The Weisfeiler-Leman (WL) algorithms form a family of incomplete approaches to the graph isomorphism problem. They recently found various applications in algorithmic group theory a…
Computational complexity of the Weisfeiler-Leman dimension
Moritz Lichter, Simon Raßmann, Pascal Schweitzer
The Weisfeiler-Leman dimension of a graph is the least number such that the -dimensional Weisfeiler-Leman algorithm distinguishes from every other non-isomorphic gra…
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-…