Graph isomorphism and theorems of Birkhoff type

DOI10.1007/BF02240204zbMath0581.05038MaRDI QIDQ1068104

Gottfried Tinhofer

Publication date: 1986

Published in: Computing (Search for Journal in Brave)

zbMATH Keywords

tree; cycle; doubly stochastic matrix; convex polytopes; graph isomorphism

Mathematics Subject Classification ID

20B25: Finite automorphism groups of algebraic, geometric, or combinatorial structures

68R10: Graph theory (including graph drawing) in computer science

05C25: Graphs and abstract algebra (groups, rings, fields, etc.)

05C50: Graphs and linear algebra (matrices, eigenvalues, etc.)

15B51: Stochastic matrices

52Bxx: Polytopes and polyhedra

Related Items

A note on certain subpolytopes of the assignment polytope associated with circulant graphs, Compact graphs and equitable partitions, 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, Isomorphism of chordal (6, 3) graphs, 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