The k-Dimensional Weisfeiler-Leman Algorithm

2019/07/22 by Neil Immerman, Rik Sengupta, Immerman, Neil +1 · 1 citation
Computer Science · Mathematics · #Complexity and Algorithms in Graphs #Advanced Graph Theory Research #Limits and Structures in Graph Theory

paper · pdf · doi:10.48550/arxiv.1907.09582

Abstract

In this note, we provide details of the k-dimensional Weisfeiler-Leman Algorithm and its analysis from Immerman-Lander (1990). In particular, we present an optimized version of the algorithm that runs in time O(n^k+1log n), where k is fixed (not varying with n).

Cited by

• Bridging Theory and Practice in Link Representation with Graph Neural Networks

Related

• Compressing CFI Graphs and Lower Bounds for the Weisfeiler-Leman Refinements
• Logarithmic Weisfeiler--Leman and Treewidth
• The probabilistic Weisfeiler-Leman algorithm
• On the Weisfeiler algorithm of depth-1 stabilization
• Computational complexity of the Weisfeiler-Leman dimension