Two reductions of graph isomorphism to problems on polynomials

DOI10.1007/BF01629437zbMath0493.03016MaRDI QIDQ1168312

Dima Yu. Grigoriev

Publication date: 1982

Published in: Journal of Soviet Mathematics (Search for Journal in Brave)

zbMATH Keywords

graph isomorphism problemdecomposition of a univariate polynomial into irreducible multipliers

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Polynomials over finite fields (11T06) Complexity of computation (including implicit computational complexity) (03D15) Graph theory (05C99)

Related Items

Applications of dimensionality reduction and exponential sums to graph automorphism ⋮ Graph isomorphism problem

Cites Work

• Graph isomorphism, general remarks
• Isomorphism problem for a class of point-symmetric structures
• The graph isomorphism disease
• FOUNDATIONS OF ALGEBRAIC GEOMETRY
• Unnamed Item
• Unnamed Item