On Tinhofer's linear programming approach to isomorphism testing

DOI10.1007/978-3-662-48054-0_3MaRDI QIDQ2946374zbMATH OpenOpenAlexFDO

Authors Vikraman Arvind, Gaurav Rattan, Oleg Verbitsky, Johannes Köbler

Publication date 16 September 2015

Published in Mathematical Foundations of Computer Science 2015 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-662-48054-0_3

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Structural characterization of families of graphs (05C75) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Linear programming (90C05)

Recommendations

• Graph isomorphism, color refinement, and compactness
• Dimension reduction via colour refinement
• A note on compact graphs
• Lov\'asz Meets Weisfeiler and Leman
• A geometric approach to graph isomorphism

Cites work

• A note on certain subpolytopes of the assignment polytope associated with circulant graphs
• A note on compact graphs
• Combinatorial matrix classes
• Compact cellular algebras and permutation groups
• Compact graphs and equitable partitions
• Equivalence in finite-variable logics is complete for polynomial time
• Forestal algebras and algebraic forests (on a new class of weakly compact graphs)
• Fractional isomorphism of graphs
• Graph isomorphism and theorems of Birkhoff type
• Graph isomorphism, color refinement, and compactness
• Graphs identified by logics with counting
• scientific article; zbMATH DE number 1890111 (Why is no real title available?)
• On compact graphs
• On the power of color refinement
• Pebble games and linear equations
• Random Graph Isomorphism
• Sherali-Adams relaxations and indistinguishability in counting logics
• Sherali-Adams relaxations of graph isomorphism polytopes
• Some applications of doubly stochastic matrices
• Strong tree-cographs are Birkhoff graphs

Cited in

(5)

• Graph isomorphism, color refinement, and compactness
• On the power of color refinement
• Условная предельная теорема для близких к критическим ветвящихся процессов с финальным типом частиц
• Linear-Time Version of Holub’s Algorithm for Morphic Imprimitivity Testing
• scientific article; zbMATH DE number 7561610 (Why is no real title available?)

This page was built for publication: On Tinhofer's linear programming approach to isomorphism testing

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