Lov\'asz Meets Weisfeiler and Leman
From MaRDI portal
Publication:5002713
DOI10.4230/LIPIcs.ICALP.2018.40zbMath1504.05276arXiv1802.08876OpenAlexW2963063614MaRDI QIDQ5002713
Martin Grohe, Gaurav Rattan, Holger Dell
Publication date: 28 July 2021
Full work available at URL: https://arxiv.org/abs/1802.08876
Graph algorithms (graph-theoretic aspects) (05C85) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)
Related Items
Perfect matchings, rank of connection tensors and graph homomorphisms, A path forward: tropicalization in extremal combinatorics, Approximating fractionally isomorphic graphons, Weisfeiler-Leman indistinguishability of graphons, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, On the expressive power of linear algebra on graphs, On Weisfeiler-Leman invariance: subgraph counts and related graph properties, The Complexity of Homomorphism Indistinguishability, The Power of the Weisfeiler-Leman Algorithm to Decompose Graphs, Fractional isomorphism of graphons, A generalized Weisfeiler-Lehman graph kernel
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The complexity of counting homomorphisms seen from the other side
- Graph isomorphism and theorems of Birkhoff type
- A note on compact graphs
- Which graphs are determined by their spectrum?
- Sherali-Adams relaxations of graph isomorphism polytopes
- Sherali--Adams Relaxations and Indistinguishability in Counting Logics
- Approximate Graph Isomorphism
- On the Maximum Quadratic Assignment Problem
- Limitations of Algebraic Approaches to Graph Isomorphism Testing
- PEBBLE GAMES AND LINEAR EQUATIONS
- Universal Covers, Color Refinement, and Two-Variable Counting Logic: Lower Bounds for the Depth
- Lower Bounds on Hilbert's Nullstellensatz and Propositional Proofs
- Graph isomorphism in quasipolynomial time [extended abstract]
- Operations with structures
