Constructing an algorithm of quadratic time complexity for finding the maximal matching
DOI:
https://doi.org/10.15587/1729-4061.2019.188104Keywords:
matching, maximal matching, bipartite graph, prolonged path, assignment problemAbstract
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 storageReferences
- 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
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2019 Andrii Morozov, Tamara Loktikova, Iurii Iefremov, Anatolii Dykyi, Pavlo Zabrodskyy
This work is licensed under a Creative Commons Attribution 4.0 International License.
The consolidation and conditions for the transfer of copyright (identification of authorship) is carried out in the License Agreement. In particular, the authors reserve the right to the authorship of their manuscript and transfer the first publication of this work to the journal under the terms of the Creative Commons CC BY license. At the same time, they have the right to conclude on their own additional agreements concerning the non-exclusive distribution of the work in the form in which it was published by this journal, but provided that the link to the first publication of the article in this journal is preserved.
A license agreement is a document in which the author warrants that he/she owns all copyright for the work (manuscript, article, etc.).
The authors, signing the License Agreement with TECHNOLOGY CENTER PC, have all rights to the further use of their work, provided that they link to our edition in which the work was published.
According to the terms of the License Agreement, the Publisher TECHNOLOGY CENTER PC does not take away your copyrights and receives permission from the authors to use and dissemination of the publication through the world's scientific resources (own electronic resources, scientometric databases, repositories, libraries, etc.).
In the absence of a signed License Agreement or in the absence of this agreement of identifiers allowing to identify the identity of the author, the editors have no right to work with the manuscript.
It is important to remember that there is another type of agreement between authors and publishers – when copyright is transferred from the authors to the publisher. In this case, the authors lose ownership of their work and may not use it in any way.
