DOI: https://doi.org/10.15587/1729-4061.2019.188104

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

Andrii Morozov, Tamara Loktikova, Iurii Iefremov, Anatolii Dykyi, Pavlo Zabrodskyy

Abstract


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

Keywords


matching; maximal matching; bipartite graph; prolonged path; assignment problem

References


Toth, P., Vigo, D. (Eds.) (2014). Vehicle Routing: Problems, Methods, and Applications. SIAM. doi: https://doi.org/10.1137/1.9781611973594

Brusco, M. J., Stahl, S. (2005). Branch-and-Bound Applications in Combinatorial Data Analysis. Springer. doi: https://doi.org/10.1007/0-387-28810-4

Coste, P., Lodi, A., Pesant, G. (2019). Using Cost-Based Solution Densities from TSP Relaxations to Solve Routing Problems. Lecture Notes in Computer Science, 182–191. doi: https://doi.org/10.1007/978-3-030-19212-9_12

Matsiy, O. B., Morozov, A. V., Panishev, A. V. (2016). Fast Algorithm to Find 2-Factor of Minimum Weight. Cybernetics and Systems Analysis, 52 (3), 467–474. doi: https://doi.org/10.1007/s10559-016-9847-9

Zenklusen, R. (2019). A 1.5-Approximation for Path TSP. Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 1539–1549. doi: https://doi.org/10.1137/1.9781611975482.93

Papadimitriu, H., Stayglits, K. (1985). Kombinatornaya optimizatsiya: Algoritmy i slozhnost'. Moscow: Mir, 510.

Edmonds, J. (1965). Paths, Trees, and Flowers. Canadian Journal of Mathematics, 17, 449–467. doi: https://doi.org/10.4153/cjm-1965-045-4

Lovas, L., Plammer, M. (1998). Prikladnye zadachi teorii grafov. Teoriya parosochetaniy v matematike, fizike, himii. Moscow: Mir, 653.

Sharifov, F. A. (2008). Sovershennye parosochetaniya i rasshirenniy polimatroid. Kibernetika i sistemniy analiz, 3, 173–179.

Öncan, T., Şuvak, Z., Akyüz, M. H., Altınel, İ. K. (2019). Assignment problem with conflicts. Computers & Operations Research, 111, 214–229. doi: https://doi.org/10.1016/j.cor.2019.07.001

Naser, H., Awad, W. S., El-Alfy, E.-S. M. (2019). A multi-matching approximation algorithm for Symmetric Traveling Salesman Problem. Journal of Intelligent & Fuzzy Systems, 36 (3), 2285–2295. doi: https://doi.org/10.3233/jifs169939


GOST Style Citations








Copyright (c) 2019 Andrii Morozov, Tamara Loktikova, Iurii Iefremov, Anatolii Dykyi, Pavlo Zabrodskyy

Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 International License.

ISSN (print) 1729-3774, ISSN (on-line) 1729-4061