Pebble games and linear equations

DOI10.4230/LIPICS.CSL.2012.289MaRDI QIDQ4649553zbMATH OpenOpenAlexFDO

Authors Martin Grohe, Martin Otto

Publication date 22 November 2012

Full work available at URL http://drops.dagstuhl.de/opus/volltexte/2012/3679/pdf/25.pdf

zbMATH Keywords

finite model theoryfinite-variable logicsgraph isomorphismlinear programmingSherali-Adams hierarchyWeisfeiler-Lehman algorithm

Mathematics Subject Classification ID

Model theory of finite structures (03C13) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Linear programming (90C05) Games involving graphs (91A43)

Recommendations

• PEBBLE GAMES AND LINEAR EQUATIONS
• Sherali-Adams relaxations and indistinguishability in counting logics
• Sherali-Adams relaxations and indistinguishability in counting logics

Cited in

(9)

• The QAP-polytope and the graph isomorphism problem
• Pebble games and cospectral graphs
• Quantum and non-signalling graph isomorphisms
• Sherali-Adams relaxations and indistinguishability in counting logics
• Sherali-Adams relaxations and indistinguishability in counting logics
• Graphs identified by logics with counting
• On Tinhofer's linear programming approach to isomorphism testing
• Limitations of algebraic approaches to graph isomorphism testing
• PEBBLE GAMES AND LINEAR EQUATIONS

This page was built for publication: Pebble games and linear equations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4649553)