pith. sign in

arxiv: 1907.09582 · v1 · pith:X6USANQ3new · submitted 2019-07-22 · 💻 cs.CC · cs.DS· math.LO

The k-Dimensional Weisfeiler-Leman Algorithm

Neil Immerman , Rik Sengupta This is my paper
classification 💻 cs.CC cs.DSmath.LO
keywords algorithmdimensionalweisfeiler-lemananalysisdetailsfixedimmerman-landernote
0
0 comments X
read the original 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+1}\log n)$, where $k$ is fixed (not varying with $n$).

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. A Hierarchy of Tinhofer Graphs: Separations and Membership Testing

    cs.CC 2026-05 unverdicted novelty 7.0

    Introduces the k-Tinhofer hierarchy between general graphs and Tinhofer graphs, gives algebraic and combinatorial characterizations, proves strict separations for each k, shows P-hardness of deciding membership in the...