Walk refinement, walk logic, and the iteration number of the Weisfeiler-Leman algorithm

DOI10.5555/3470152.3470185MaRDI QIDQ6654499FDOQ6654499

Authors: Ilya Ponomarenko, P. Schweitzer 

Publication date: 19 December 2024

Recommendations

• scientific article; zbMATH DE number 1754602
• Near-Optimal Lower Bounds on Quantifier Depth and Weisfeiler--Leman Refinement Steps

zbMATH Keywords

first-order logiccounting quantifiersquantifier depthWeisfeiler-Leman algorithm

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Model theory of finite structures (03C13) Coloring of graphs and hypergraphs (05C15) Enumeration in graph theory (05C30) Logic in computer science (03B70)

This page was built for publication: Walk refinement, walk logic, and the iteration number of the Weisfeiler-Leman algorithm

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6654499)