The Power of the Weisfeiler--Leman Algorithm to Decompose Graphs

DOI10.1137/20M1314987zbMath1493.68273arXiv1908.05268MaRDI QIDQ5028356

Daniel Neuen, Sandra Kiefer

Publication date: 9 February 2022

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

dynamic programmingtime complexitygraph decompositiongraph isomorphismWeisfeiler-Leman algorithm

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items (1)

Canonisation and Definability for Graphs of Bounded Rank Width

Uses Software

• nauty
• Traces

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
• Treewidth. Computations and approximations
• On the connectivity of graphs in association schemes
• Logical hierarchies in PTIME
• A V log V algorithm for isomorphism of triconnected planar graphs
• Positive-instance driven dynamic programming for treewidth
• Practical graph isomorphism. II.
• \(A\,V^ 2\) algorithm for determining isomorphism of planar graphs
• Sherali--Adams Relaxations and Indistinguishability in Counting Logics
• On recognizing graphs by numbers of homomorphisms
• 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)
• The Weisfeiler--Leman Dimension of Planar Graphs Is at Most 3
• 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