Impact Factor

Dmitry Malyshev

ul. Gagarina 23, Nizhny Novgorod, 603950 Russia
Nizhnii Novgorod State University


Grines V. Z., Malyshev D. S., Pochinka O. V., Zinina S. K.
Efficient Algorithms for the Recognition of Topologically Conjugate Gradient-like Diffeomorhisms
2016, vol. 21, no. 2, pp.  189-203
It is well known that the topological classification of structurally stable flows on surfaces as well as the topological classification of some multidimensional gradient-like systems can be reduced to a combinatorial problem of distinguishing graphs up to isomorphism. The isomorphism problem of general graphs obviously can be solved by a standard enumeration algorithm. However, an efficient algorithm (i. e., polynomial in the number of vertices) has not yet been developed for it, and the problem has not been proved to be intractable (i. e., NPcomplete). We give polynomial-time algorithms for recognition of the corresponding graphs for two gradient-like systems. Moreover, we present efficient algorithms for determining the orientability and the genus of the ambient surface. This result, in particular, sheds light on the classification of configurations that arise from simple, point-source potential-field models in efforts to determine the nature of the quiet-Sun magnetic field.
Keywords: Morse – Smale diffeomorphism, gradient-like diffeomorphism, topological classification, three-color graph, directed graph, graph isomorphism, surface orientability, surface genus, polynomial-time algorithm, magnetic field
Citation: Grines V. Z., Malyshev D. S., Pochinka O. V., Zinina S. K.,  Efficient Algorithms for the Recognition of Topologically Conjugate Gradient-like Diffeomorhisms, Regular and Chaotic Dynamics, 2016, vol. 21, no. 2, pp. 189-203

Back to the list