Graph isomorphism and theorems of Birkhoff type

DOI10.1007/BF02240204zbMath0581.05038OpenAlexW145923007MaRDI QIDQ1068104

Gottfried Tinhofer

Publication date: 1986

Published in: Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf02240204

zbMATH Keywords

treecycledoubly stochastic matrixconvex polytopesgraph isomorphism

Mathematics Subject Classification ID

Finite automorphism groups of algebraic, geometric, or combinatorial structures (20B25) Graph theory (including graph drawing) in computer science (68R10) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Stochastic matrices (15B51) Polytopes and polyhedra (52Bxx)

Related Items

Fractional isomorphism of graphs, Limitations of Algebraic Approaches to Graph Isomorphism Testing, On permutation polytopes, PEBBLE GAMES AND LINEAR EQUATIONS, Isomorphism of chordal (6, 3) graphs, Some applications of doubly stochastic matrices, Strong tree-cographs are Birkhoff graphs, Dynamical systems associated with adjacency matrices, Lov\'asz Meets Weisfeiler and Leman, Consolidation for compact constraints and Kendall tau LP decodable permutation codes, Graph isomorphism, color refinement, and compactness, On Tinhofer’s Linear Programming Approach to Isomorphism Testing, On the Power of Color Refinement, Definable Ellipsoid Method, Sums-of-Squares Proofs, and the Graph Isomorphism Problem, Quantum and non-signalling graph isomorphisms, Approximating fractionally isomorphic graphons, Weisfeiler-Leman indistinguishability of graphons, Directed path graph isomorphism, A note on compact graphs, Compact graphs and equitable partitions, On the Weisfeiler-Leman dimension of fractional packing, Unnamed Item, A note on certain subpolytopes of the assignment polytope associated with circulant graphs, On the expressive power of linear algebra on graphs, Convex Hulls of Algebraic Sets, Faces of Birkhoff Polytopes, Compact cellular algebras and permutation groups, Fractional isomorphism of graphons, Sherali-Adams relaxations of graph isomorphism polytopes, On compact graphs

Cites Work

• A new polynomial-time algorithm for linear programming
• The ellipsoid method and its consequences in combinatorial optimization
• Convex polyhedra of doubly stochastic matrices. II: Graph of Omega sub(n)
• Convex polyhedra of doubly stochastic matrices. I: Applications of the permanent function
• Further annotated bibliography on the isomorphism disease
• Results and problems in the theory of doubly-stochastic matrices
• The graph isomorphism disease
• An Efficient Algorithm for Graph Isomorphism