|
Zapiski Nauchnykh Seminarov LOMI, 1979, Volume 88, Pages 56–61
(Mi znsl3102)
|
|
|
|
This article is cited in 5 scientific papers (total in 5 papers)
Two reductions of graph isomorphism to problems for polynomials
D. Yu. Grigor'ev
Abstract:
The problem of isomorphism of $n$-vertices graphs with weights on their edges possesses a full system of invariants which consists of $(n^2+1)$ polynomials of degree $\leq n^2$ (theorem 1). The proof of existence of such a system is not effective and is based on the primitive element theorem. Theorem 2 asserts that the graph isomorphism problem (or even the problem of divising the set of vertices of a graph $T$ on the domains of transitivity) can be reduced in polynomial time to the problem of decomposition of some univariable polynomial $f$ into irreducible multipliers over some field $F_T$ (the coefficients of $f$ depend only on
the number of vertices of $T$).
Citation:
D. Yu. Grigor'ev, “Two reductions of graph isomorphism to problems for polynomials”, Studies in constructive mathematics and mathematical logic. Part VIII, Zap. Nauchn. Sem. LOMI, 88, "Nauka", Leningrad. Otdel., Leningrad, 1979, 56–61; J. Soviet Math., 20:4 (1982), 2296–2298
Linking options:
https://www.mathnet.ru/eng/znsl3102 https://www.mathnet.ru/eng/znsl/v88/p56
|
Statistics & downloads: |
Abstract page: | 230 | Full-text PDF : | 76 |
|