|
This article is cited in 6 scientific papers (total in 6 papers)
Efficient Algorithms for the Recognition of Topologically Conjugate Gradient-like Diffeomorhisms
Vyacheslav Z. Grinesa, Dmitry S. Malyshevab, Olga V. Pochinkaa, Svetlana Kh. Zininac a National Research University Higher School of Economics, ul. Bolshaya Pecherskaya 25/12, Nizhny Novgorod, 603155, Russia
b N. I. Lobachevsky State University of Nizhni Novgorod, ul. Gagarina 23, Nizhny Novgorod, 603950, Russia
c Ogarev Mordovia State University, ul. Bolshevistskaya 68, Saransk, 430005, Russia
Abstract:
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.
Received: 08.12.2015 Accepted: 04.02.2016
Citation:
Vyacheslav Z. Grines, Dmitry S. Malyshev, Olga V. Pochinka, Svetlana Kh. Zinina, “Efficient Algorithms for the Recognition of Topologically Conjugate Gradient-like Diffeomorhisms”, Regul. Chaotic Dyn., 21:2 (2016), 189–203
Linking options:
https://www.mathnet.ru/eng/rcd74 https://www.mathnet.ru/eng/rcd/v21/i2/p189
|
Statistics & downloads: |
Abstract page: | 274 | References: | 39 |
|