The Power of the Weisfeiler-Leman Algorithm to Decompose Graphs

DOI10.4230/LIPICS.MFCS.2019.45OpenAlexW2970802938MaRDI QIDQ5092407FDOQ5092407

Authors: Sandra Kiefer, Daniel Neuen 

Publication date: 21 July 2022

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

Recommendations

• The power of the Weisfeiler-Leman algorithm to decompose graphs
• The Weisfeiler--Leman Dimension of Planar Graphs Is at Most 3
• On the Weisfeiler-Leman dimension of fractional packing
• The Weisfeiler-Leman algorithm and recognition of graph properties
• The Weisfeiler-Leman dimension of planar graphs is at most 3

zbMATH Keywords

first-order logicseparatorscounting quantifiersWeisfeiler-Leman

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Practical graph isomorphism. II.
• Title not available (Why is that?)
• Complexity of Finding Embeddings in a k-Tree
• Fixed-point definability and polynomial time on graphs with excluded minors
• An optimal lower bound on the number of variables for graph identification
• Title not available (Why is that?)
• Title not available (Why is that?)
• Dividing a Graph into Triconnected Components
• Title not available (Why is that?)
• The vertex-connectivity of a distance-regular graph
• The connectivity of strongly regular graphs
• On the connectivity of graphs in association schemes
• A V log V algorithm for isomorphism of triconnected planar graphs
• Sherali-Adams relaxations and indistinguishability in counting logics
• Graph isomorphism in quasipolynomial time (extended abstract)
• Logical hierarchies in PTIME
• Isomorphism of planar graphs (working paper)
• \(A\,V^ 2\) algorithm for determining isomorphism of planar graphs
• The Power of Counting Logics on Restricted Classes of Finite Structures
• PEBBLE GAMES AND LINEAR EQUATIONS
• Lov\'asz Meets Weisfeiler and Leman
• On the combinatorial power of the Weisfeiler-Lehman algorithm
• Descriptive Complexity, Canonisation, and Definable Graph Structure Theory
• The Weisfeiler-Leman dimension of planar graphs is at most 3
• Graph isomorphism for unit square graphs
• On Weisfeiler-Leman invariance: subgraph counts and related graph properties

Cited In (5)

• The Weisfeiler--Leman Dimension of Planar Graphs Is at Most 3
• The Weisfeiler-Leman dimension of distance-hereditary graphs
• On the Weisfeiler-Leman dimension of fractional packing
• On the complexity of identifying strongly regular graphs
• On the Power of the Semi-Separated Pair Decomposition

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

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