|
Trudy Instituta Matematiki i Mekhaniki UrO RAN, 2016, Volume 22, Number 1, Pages 235–240
(Mi timm1275)
|
|
|
|
Reduction of the graph isomorphism problem to checking the equality of polynomials of $n$ variables
A. V. Prolubnikov Omsk State University
Abstract:
It is proved that two graphs are isomorphic if there exists an enumeration for vertices of one of the graphs such that modified characteristic polynomials of the graphs are equal. An algorithm for solving the graph isomorphism problem is presented. The algorithm finds an enumeration for vertices of one of the graphs that provides the equality of coefficients of the polynomials if such an enumeration exists.
Keywords:
graph isomorphism, complete invariant.
Received: 26.12.2014
Citation:
A. V. Prolubnikov, “Reduction of the graph isomorphism problem to checking the equality of polynomials of $n$ variables”, Trudy Inst. Mat. i Mekh. UrO RAN, 22, no. 1, 2016, 235–240
Linking options:
https://www.mathnet.ru/eng/timm1275 https://www.mathnet.ru/eng/timm/v22/i1/p235
|
Statistics & downloads: |
Abstract page: | 199 | Full-text PDF : | 91 | References: | 49 | First page: | 25 |
|