Аннотация:
Доказывается, что для изоморфизма n-вершинных графов с весами на ребрах существует полная система из n2+1 полиномиального инварианта. Показано также, что изоморфизм графов сводится в полиномиальное время к разложению полинома от одной переменной на неприводимые над некоторым полем множители. Библ. – 9 назв.
Образец цитирования:
Д. Ю. Григорьев, “Два сведе́ния изоморфизма графов к задачам о полиномах”, Исследования по конструктивной математике и математической логике. VIII, Зап. научн. сем. ЛОМИ, 88, Изд-во «Наука», Ленинград. отд., Л., 1979, 56–61; J. Soviet Math., 20:4 (1982), 2296–2298
\RBibitem{Gri79}
\by Д.~Ю.~Григорьев
\paper Два свед\'ения изоморфизма графов к~задачам о~полиномах
\inbook Исследования по конструктивной математике и математической логике.~VIII
\serial Зап. научн. сем. ЛОМИ
\yr 1979
\vol 88
\pages 56--61
\publ Изд-во «Наука», Ленинград. отд.
\publaddr Л.
\mathnet{http://mi.mathnet.ru/znsl3102}
\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=556219}
\zmath{https://zbmath.org/?q=an:0429.03021|0493.03016}
\transl
\jour J. Soviet Math.
\yr 1982
\vol 20
\issue 4
\pages 2296--2298
\crossref{https://doi.org/10.1007/BF01629437}
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/znsl3102
https://www.mathnet.ru/rus/znsl/v88/p56
Эта публикация цитируется в следующих 5 статьяx:
А. В. Пролубников, “Сведение задачи проверки изоморфизма графов к задаче проверки равенства полиномов от n переменных”, Тр. ИММ УрО РАН, 22, № 1, 2016, 235–240
A. L. Chistov, “Algorithm of polynomial complexity for factoring polynomials and finding the components of varieties in subexponential time”, J Math Sci, 34:4 (1986), 1838
D. Yu. Grigor'ev, “Factorization of polynomials over a finite field and the solution of systems of algebraic equations”, J Math Sci, 34:4 (1986), 1762
V. N. Zemlyachenko, N. M. Korneenko, R. I. Tyshkevich, “Graph isomorphism problem”, J Math Sci, 29:4 (1985), 1426
А. О. Слисенко, “Сложностные задачи теории вычислений”, УМН, 36:6(222) (1981), 21–103; A. O. Slisenko, “Complexity problems in computational theory”, Russian Math. Surveys, 36:6 (1981), 23–125
Цитирование в формате AMSBIB
Обратная связь: