Canonisation and Definability for Graphs of Bounded Rank Width
From MaRDI portal
Cites work
- An improved isomorphism test for bounded-tree-width graphs
- An optimal lower bound on the number of variables for graph identification
- Approximating clique-width and branch-width
- Computing with tangles
- Definable decompositions for graphs of bounded linear cliquewidth
- Descriptive Complexity, Canonisation, and Definable Graph Structure Theory
- Elements of finite model theory.
- Expressive equivalence of least and inflationary fixed-point logic
- Finite model theory and its applications.
- Fixed-Parameter Tractable Canonization and Isomorphism Test for Graphs of Bounded Treewidth
- Fixed-point extensions of first-order logic
- Forestal algebras and algebraic forests (on a new class of weakly compact graphs)
- Graph isomorphism in quasipolynomial time (extended abstract)
- Graph minors. X: Obstructions to tree-decomposition
- Handle-rewriting hypergraph grammars
- scientific article; zbMATH DE number 1254648 (Why is no real title available?)
- scientific article; zbMATH DE number 1324669 (Why is no real title available?)
- scientific article; zbMATH DE number 515737 (Why is no real title available?)
- scientific article; zbMATH DE number 979011 (Why is no real title available?)
- scientific article; zbMATH DE number 2044928 (Why is no real title available?)
- scientific article; zbMATH DE number 809155 (Why is no real title available?)
- scientific article; zbMATH DE number 1392292 (Why is no real title available?)
- scientific article; zbMATH DE number 7561610 (Why is no real title available?)
- Isomorphism of graphs of bounded valence can be tested in polynomial time
- Isomorphism testing for embeddable graphs through definability
- Languages that Capture Complexity Classes
- Linear time solvable optimization problems on graphs of bounded clique-width
- Logical hierarchies in PTIME
- Polynomial algorithms for graph isomorphism and chromatic index on partial k-trees
- Rank-width and vertex-minors
- Rank‐width is less than or equal to branch‐width
- Solving linear programs without breaking abstractions
- Structure and complexity of relational queries
- Structure theorem and isomorphism test for graphs with excluded topological subgraphs
- The monadic second-order logic of graphs. VIII: Orientations
- The power of the Weisfeiler-Leman algorithm to decompose graphs
- The Weisfeiler--Leman Dimension of Planar Graphs Is at Most 3
- Upper bounds to the clique width of graphs
Cited in
(15)- Recognizability equals definability for graphs of bounded treewidth and bounded chordality
- The Weisfeiler--Leman Dimension of Planar Graphs Is at Most 3
- The Weisfeiler-Leman dimension of distance-hereditary graphs
- Faster isomorphism for p-groups of class 2 and exponent p
- Choiceless polynomial time with witnessed symmetric choice
- The Ackermann encoding and its siblings
- On the descriptive complexity of groups without abelian normal subgroups
- Isomorphism for tournaments of small twin width
- On the parallel complexity of group isomorphism via Weisfeiler-Leman
- Canonizing graphs of bounded rank-width in parallel via Weisfeiler-Leman
- Bounding the Weisfeiler-Leman dimension via a depth analysis of I/R-trees
- Separating rank logic from polynomial time
- Computational complexity of the Weisfeiler-Leman dimension
- Finite variable counting logics with restricted requantification
- Computational complexity of the Weisfeiler-Leman dimension
This page was built for publication: Canonisation and Definability for Graphs of Bounded Rank Width
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5875948)
