Canonisation and Definability for Graphs of Bounded Rank Width

DOI10.1145/3568025OpenAlexW2913482449MaRDI QIDQ5875948

Daniel Neuen, Martin Grohe

Publication date: 7 February 2023

Published in: ACM Transactions on Computational Logic (Search for Journal in Brave)

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

zbMATH Keywords

Weisfeiler-Leman algorithmfixed-point logic with countingcanonisationrank width

Mathematics Subject Classification ID

Logic in computer science (03B70) Computer science (68-XX)

Related Items (1)

The Weisfeiler-Leman dimension of distance-hereditary graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Finite model theory and its applications.
• Elements of finite model theory.
• Fixed-point extensions of first-order logic
• Isomorphism of graphs of bounded valence can be tested in polynomial time
• Graph minors. X: Obstructions to tree-decomposition
• An optimal lower bound on the number of variables for graph identification
• Forestal algebras and algebraic forests (on a new class of weakly compact graphs)
• Logical hierarchies in PTIME
• Structure and complexity of relational queries
• The monadic second-order logic of graphs. VIII: Orientations
• Expressive equivalence of least and inflationary fixed-point logic
• Linear time solvable optimization problems on graphs of bounded clique-width
• Upper bounds to the clique width of graphs
• Handle-rewriting hypergraph grammars
• Approximating clique-width and branch-width
• Rank-width and vertex-minors
• Fixed-Parameter Tractable Canonization and Isomorphism Test for Graphs of Bounded Treewidth
• Solving Linear Programs without Breaking Abstractions
• Isomorphism testing for embeddable graphs through definability
• Polynomial algorithms for graph isomorphism and chromatic index on partial k-trees
• Languages that Capture Complexity Classes
• An Improved Isomorphism Test for Bounded-tree-width Graphs
• The Power of the Weisfeiler--Leman Algorithm to Decompose Graphs
• The Weisfeiler--Leman Dimension of Planar Graphs Is at Most 3
• Structure Theorem and Isomorphism Test for Graphs with Excluded Topological Subgraphs
• Descriptive Complexity, Canonisation, and Definable Graph Structure Theory
• Graph isomorphism in quasipolynomial time [extended abstract]
• Rank‐width is less than or equal to branch‐width
• Computing with Tangles

This page was built for publication: Canonisation and Definability for Graphs of Bounded Rank Width