1 citations · 2 across the 2 of their papers we have counts for
8 papers
The Weisfeiler-Leman Algorithm and Recognition of Graph Properties
Frank Fuhlbrück, Johannes Köbler, Ilia Ponomarenko +1
The -dimensional Weisfeiler-Leman algorithm (-WL) is a very useful combinatorial tool in graph isomorphism testing. We address the applicability of -WL to recognition of g…
Local WL Invariance and Hidden Shades of Regularity
Frank Fuhlbrück, Johannes Köbler, Oleg Verbitsky
The -dimensional Weisfeiler-Leman algorithm is a powerful tool in graph isomorphism testing. For an input graph , the algorithm determines a canonical coloring of -tuples…
On the Weisfeiler-Leman Dimension of Fractional Packing
V. Arvind, Frank Fuhlbrück, Johannes Köbler +1
The -dimensional Weisfeiler-Leman procedure (-WL), which colors -tuples of vertices in rounds based on the neighborhood structure in the graph, has proven to be immensely…
Identifiability of Graphs with Small Color Classes by the Weisfeiler-Leman Algorithm
Frank Fuhlbrück, Johannes Köbler, Oleg Verbitsky
As it is well known, the isomorphism problem for vertex-colored graphs with color multiplicity at most 3 is solvable by the classical 2-dimensional Weisfeiler-Leman algorithm (2-WL…
On Weisfeiler-Leman Invariance: Subgraph Counts and Related Graph Properties
V. Arvind, Frank Fuhlbrück, Johannes Köbler +1
The -dimensional Weisfeiler-Leman algorithm (-WL) is a fruitful approach to the Graph Isomorphism problem. 2-WL corresponds to the original algorithm suggested by Weisfeiler…
Finding Small Weight Isomorphisms with Additional Constraints is Fixed-Parameter Tractable
V. Arvind, Johannes Köbler, Sebastian Kuhnert +1
Lubiw showed that several variants of Graph Isomorphism are NP-complete, where the solutions are required to satisfy certain additional constraints [SICOMP 10, 1981]. One of these,…