On the Combinatorial Power of the Weisfeiler-Lehman Algorithm

DOI10.1007/978-3-319-57586-5_22zbMath1489.05146arXiv1704.01023OpenAlexW2605912794MaRDI QIDQ5283372

Martin Fuerer

Publication date: 21 July 2017

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1704.01023

zbMATH Keywords

graph invariantsgraph isomorphismWeisfeiler-Lehman algorithmcounting cycles

Mathematics Subject Classification ID

Enumeration in graph theory (05C30) Paths and cycles (05C38) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (13)

Nonlocal games and quantum permutation groups ⋮ Almost all trees have quantum symmetry ⋮ Subjectively interesting connecting trees and forests ⋮ Local WL invariance and hidden shades of regularity ⋮ Unnamed Item ⋮ Unnamed Item ⋮ On the expressive power of linear algebra on graphs ⋮ On Weisfeiler-Leman invariance: subgraph counts and related graph properties ⋮ The Power of the Weisfeiler-Leman Algorithm to Decompose Graphs ⋮ The Weisfeiler-Leman algorithm and recognition of graph properties ⋮ The Weisfeiler-Leman algorithm and recognition of graph properties ⋮ Identifiability of Graphs with Small Color Classes by the Weisfeiler--Leman Algorithm ⋮ The Power of the Weisfeiler--Leman Algorithm to Decompose Graphs

Cites Work

• Unnamed Item
• Spectra of symmetric powers of graphs and the Weisfeiler-Lehman refinements
• Finding and counting given length cycles
• On the power of combinatorial and spectral invariants
• 6-transitive graphs
• Isomorphism of graphs of bounded valence can be tested in polynomial time
• An optimal lower bound on the number of variables for graph identification
• On construction and identification of graphs. With contributions by A. Lehman, G. M. Adelson-Velsky, V. Arlazarov, I. Faragev, A. Uskov, I. Zuev, M. Rosenfeld and B. Weisfeiler
• Random Graph Isomorphism
• The graph isomorphism disease
• The Parameterized Complexity of Counting Problems
• Graph isomorphism in quasipolynomial time [extended abstract]
• Multiplying matrices faster than coppersmith-winograd

This page was built for publication: On the Combinatorial Power of the Weisfeiler-Lehman Algorithm