Dmitry Malyshev
ul. Gagarina 23, Nizhny Novgorod, 603950 Russia
Nizhnii Novgorod State University
Publications:
Grines V. Z., Malyshev D. S., Pochinka O. V., Zinina S. K.
Efficient Algorithms for the Recognition of Topologically Conjugate Gradientlike Diffeomorhisms
2016, vol. 21, no. 2, pp. 189203
Abstract
It is well known that the topological classification of structurally stable flows on surfaces as well as the topological classification of some multidimensional gradientlike 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 polynomialtime algorithms for recognition of the corresponding graphs for two gradientlike 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, pointsource potentialfield models in efforts to determine the nature of the quietSun magnetic field.
