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

Authors

DOI:

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

Keywords:

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

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

Author Biographies

Andrii Morozov, Zhytomyr Polytechnic State University Chudnivska str., 103, Zhytomyr, Ukraine, 10005

PhD, Associate Professor, Vice Rector in Scientific and Pedagogical Work

Department of Computer Science

Tamara Loktikova, Zhytomyr Polytechnic State University Chudnivska str., 103, Zhytomyr, Ukraine, 10005

Senior Lecturer

Department of Software Engineering

Iurii Iefremov, Zhytomyr Polytechnic State University Chudnivska str., 103, Zhytomyr, Ukraine, 10005

PhD, Associate Professor

Department of Software Engineering

Anatolii Dykyi, Zhytomyr Polytechnic State University Chudnivska str., 103, Zhytomyr, Ukraine, 10005

PhD, Associate Professor

Department of Economic Security, Public Administration and Management

Pavlo Zabrodskyy, Zhytomyr National Agroecological University Staryi blvd., 7, Zhytomyr, Ukraine, 10008

PhD, Associate Professor

Department of Mechanics and Agroecosystems Engineering

References

  1. Toth, P., Vigo, D. (Eds.) (2014). Vehicle Routing: Problems, Methods, and Applications. SIAM. doi: https://doi.org/10.1137/1.9781611973594
  2. 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
  3. 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
  4. 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
  5. 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
  6. Papadimitriu, H., Stayglits, K. (1985). Kombinatornaya optimizatsiya: Algoritmy i slozhnost'. Moscow: Mir, 510.
  7. Edmonds, J. (1965). Paths, Trees, and Flowers. Canadian Journal of Mathematics, 17, 449–467. doi: https://doi.org/10.4153/cjm-1965-045-4
  8. Lovas, L., Plammer, M. (1998). Prikladnye zadachi teorii grafov. Teoriya parosochetaniy v matematike, fizike, himii. Moscow: Mir, 653.
  9. Sharifov, F. A. (2008). Sovershennye parosochetaniya i rasshirenniy polimatroid. Kibernetika i sistemniy analiz, 3, 173–179.
  10. Ö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
  11. 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

2019-12-18

How to Cite

Morozov, A., Loktikova, T., Iefremov, I., Dykyi, A., & Zabrodskyy, P. (2019). Constructing an algorithm of quadratic time complexity for finding the maximal matching. Eastern-European Journal of Enterprise Technologies, 6(4 (102), 21–28. https://doi.org/10.15587/1729-4061.2019.188104

Issue

Section

Mathematics and Cybernetics - applied aspects