The Power of the Weisfeiler-Leman Algorithm to Decompose Graphs

DOI10.4230/LIPIcs.MFCS.2019.45OpenAlexW2970802938MaRDI QIDQ5092407

Sandra Kiefer, Daniel Neuen

Publication date: 21 July 2022

Full work available at URL: https://doi.org/10.4230/LIPIcs.MFCS.2019.45

zbMATH Keywords

first-order logicseparatorscounting quantifiersWeisfeiler-Leman

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Related Items (2)

Unnamed Item ⋮ On the Weisfeiler-Leman dimension of fractional packing

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The vertex-connectivity of a distance-regular graph
• The connectivity of strongly regular graphs
• An optimal lower bound on the number of variables for graph identification
• On the connectivity of graphs in association schemes
• Logical hierarchies in PTIME
• A V log V algorithm for isomorphism of triconnected planar graphs
• Practical graph isomorphism. II.
• \(A\,V^ 2\) algorithm for determining isomorphism of planar graphs
• Sherali--Adams Relaxations and Indistinguishability in Counting Logics
• PEBBLE GAMES AND LINEAR EQUATIONS
• The Power of Counting Logics on Restricted Classes of Finite Structures
• Complexity of Finding Embeddings in a k-Tree
• Graph Isomorphism for unit square graphs
• Dividing a Graph into Triconnected Components
• Isomorphism of Planar Graphs (Working Paper)
• Lov\'asz Meets Weisfeiler and Leman
• On the Combinatorial Power of the Weisfeiler-Lehman Algorithm
• Descriptive Complexity, Canonisation, and Definable Graph Structure Theory
• Graph isomorphism in quasipolynomial time [extended abstract]
• Fixed-point definability and polynomial time on graphs with excluded minors
• On Weisfeiler-Leman invariance: subgraph counts and related graph properties

This page was built for publication: The Power of the Weisfeiler-Leman Algorithm to Decompose Graphs