Redirigiendo al acceso original de articulo en 16 segundos...
ARTÍCULO
TITULO

Constructing an algorithm of quadratic time complexity for finding the maximal matching

Andrii Morozov    
Tamara Loktikova    
Iurii Iefremov    
Anatolii Dykyi    
Pavlo Zabrodskyy    

Resumen

By advancing the idea of finding width in bipartite graphs and basic definitions in matching theory, this paper shows that the task on establishing a maximal matching in an arbitrary graph can be reduced to its bipartite case. It has been proven that each current matching in an arbitrary graph is mutually consistent with the matching in a bipartite graph. It is demonstrated that each of the current solutions to the problem on establishing a maximum matching in an arbitrary graph is not lost when moving to the iterative scheme of establishing the maximum matching in a bipartite graph.To find a prolonged path relative to the fixed matching of power k, it has been proposed a modification to known algorithm for finding paths from this a given vertex to all attainable vertices of the arbitrary graph. Performance of the proposed modification has been illustrated using an example.Based on the ideas outlined, the proven statements, the proposed algorithms and their modifications, an algorithm has been constructed for finding the maximum matching with an improved time estimate compared to the known Edmons algorithm, which possesses a temporal assessment of complexity O(n4). The main drawback of the Edmons algorithm is the use of laborious procedure for compressing the odd-length cycles called "flowers", which renders the algorithm unsuitable for use in real-scale systems. Other known algorithms differ from the Edmons algorithm only by a better data storage and computational organization, while maintaining complex actions in detecting and packaging the odd-length cycles.The proposed approach of moving from an arbitrary graph to a bipartite graph prevented the occurrence of odd-length cycles, which has made it possible to significantly improve the algorithm efficiency. Further performance improvement is possible by building parallel versions of the algorithm and the optimal arrangement of data storage

 Artículos similares

       
 
Tian Wang, Zhenbo Liu, Jixing Li, Yu Liu, Xingyu Ma and Jiong Yang    
Manually preparing the data for the analysis of the calculation of a pipe network of air-cooled turbine blades is inefficient. In this paper, a method to adaptively divide the blade model and extract data of the flow units is proposed. In this method, th... ver más
Revista: Aerospace

 
Alexander Yu. Morozov and Dmitry L. Reviznikov    
Problems with interval uncertainties arise in many applied fields. The authors have earlier developed, tested, and proved an adaptive interpolation algorithm for solving this class of problems. The algorithm?s idea consists of constructing a piecewise po... ver más
Revista: Computation

 
Ekaterina Antipova and Sergey Rashkovskiy    
Within the framework of the mathematical theory of conflicts, we consider a multi-criterial conflict situation using the example of a child?parent conflict. A general method for constructing a conflict diagram is described and possible ways of the confli... ver más
Revista: Information

 
Yongsheng Yang, Qi Zhang, Minzhen Wang, Xinheng Wang and Entie Qi    
Aiming at the difficulty of fault location of multi-source transmission lines, this paper proposes a fault location method for multi-terminal transmission lines based on a fault branch judgment matrix. The fault traveling wave signal is decomposed by Com... ver más
Revista: Applied Sciences

 
Kai Cao, Yangquan Chen, Song Gao, Haixin Dang and Di An    
Multi-robot coverage systems are widely used in operations such as environmental monitoring, disaster rescue, and pollution prevention. This study considers inherent positioning errors in positioning systems and ground mobile robots with limited communic... ver más
Revista: Applied Sciences