Publication:4635884: Difference between revisions
From MaRDI portal
Publication:4635884
Created automatically from import240129110113 |
EloiFerrer (talk | contribs) m EloiFerrer moved page Upper Bounds on the Quantifier Depth for Graph Differentiation in First Order Logic to Upper Bounds on the Quantifier Depth for Graph Differentiation in First Order Logic: Duplicate |
(No difference)
|
Latest revision as of 16:07, 2 May 2024
DOI10.1145/2933575.2933595zbMath1394.68162arXiv1605.03480OpenAlexW2964195552MaRDI QIDQ4635884
Sandra Kiefer, Pascal Schweitzer
Publication date: 23 April 2018
Published in: Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1605.03480
Graph algorithms (graph-theoretic aspects) (05C85) Logic with extra quantifiers and operators (03C80) Model theory of finite structures (03C13) Descriptive complexity and finite models (68Q19)
Related Items
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- An optimal lower bound on the number of variables for graph identification
- Practical graph isomorphism. II.
- Tight Lower and Upper Bounds for the Complexity of Canonical Colour Refinement
- Dimension Reduction via Colour Refinement
- Graphs Identified by Logics with Counting
- Conflict Propagation and Component Recursion for Canonical Labeling
- Logical complexity of graphs: a survey
- From Invariants to Canonization in Parallel
- Random Graph Isomorphism
- Universal Covers, Color Refinement, and Two-Variable Counting Logic: Lower Bounds for the Depth
- Near-Optimal Lower Bounds on Quantifier Depth and Weisfeiler--Leman Refinement Steps
- Graph isomorphism in quasipolynomial time [extended abstract]
- Fixed-point definability and polynomial time on graphs with excluded minors