Fixed-point definability and polynomial time on graphs with excluded minors
From MaRDI portal
Publication:5395695
DOI10.1145/2371656.2371662zbMath1281.68129OpenAlexW2045027298MaRDI QIDQ5395695
Publication date: 17 February 2014
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/2371656.2371662
Graph minors (05C83) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Descriptive complexity and finite models (68Q19)
Related Items (15)
On symmetric circuits and fixed-point logics ⋮ Choiceless Polynomial Time on Structures with Small Abelian Colour Classes ⋮ Is Polynomial Time Choiceless? ⋮ Order Reconfiguration under Width Constraints ⋮ Upper Bounds on the Quantifier Depth for Graph Differentiation in First Order Logic ⋮ Fixed-Point Definability and Polynomial Time on Chordal Graphs and Line Graphs ⋮ Unnamed Item ⋮ On Weisfeiler-Leman invariance: subgraph counts and related graph properties ⋮ The Power of the Weisfeiler-Leman Algorithm to Decompose Graphs ⋮ The Weisfeiler-Leman algorithm and recognition of graph properties ⋮ The Weisfeiler-Leman algorithm and recognition of graph properties ⋮ Structure Theorem and Isomorphism Test for Graphs with Excluded Topological Subgraphs ⋮ Classical symmetries and the quantum approximate optimization algorithm ⋮ The Power of the Weisfeiler--Leman Algorithm to Decompose Graphs ⋮ Number of nodal domains of eigenfunctions on non-positively curved surfaces with concave boundary
This page was built for publication: Fixed-point definability and polynomial time on graphs with excluded minors
