On Tinhofer’s Linear Programming Approach to Isomorphism Testing
Publication:2946374
DOI10.1007/978-3-662-48054-0_3zbMath1465.05116OpenAlexW1475836543MaRDI QIDQ2946374
Oleg Verbitsky, V. Arvind, Gaurav Rattan, 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
Analysis of algorithms and problem complexity (68Q25) Linear programming (90C05) Structural characterization of families of graphs (05C75) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)
Related Items (4)
Cites Work
- Unnamed Item
- Unnamed Item
- A note on certain subpolytopes of the assignment polytope associated with circulant graphs
- Compact graphs and equitable partitions
- Graph isomorphism and theorems of Birkhoff type
- Some applications of doubly stochastic matrices
- Strong tree-cographs are Birkhoff graphs
- A note on compact graphs
- Compact cellular algebras and permutation groups
- Fractional isomorphism of graphs
- Forestal algebras and algebraic forests (on a new class of weakly compact graphs)
- Equivalence in finite-variable logics is complete for polynomial time
- Sherali-Adams relaxations of graph isomorphism polytopes
- Graph isomorphism, color refinement, and compactness
- On compact graphs
- Sherali--Adams Relaxations and Indistinguishability in Counting Logics
- Graphs Identified by Logics with Counting
- On the Power of Color Refinement
- Random Graph Isomorphism
- Pebble Games and Linear Equations
This page was built for publication: On Tinhofer’s Linear Programming Approach to Isomorphism Testing
