Issue 1 (191), article 2
DOI:https://doi.org/10.15407/kvt191.01.032
Kibern. vyčisl. teh., 2018, Issue 1 (191), pp.
Kyyko V.M., PhD (Engineering),
Senior Researcher of Pattern Recognition Department
e-mail: vkiiko@gmail.com
International Research and Training Center
for Information Technologies and Systems
of the National Academy of Sciences of Ukraine
and Ministry of Education and Science of Ukraine,
Acad. Glushkov av., 40, Kiev, 03187, Ukraine
MAXIMUM MATCHING IN WEIGHTED BIPARTITE GRAPHS
Introduction. The most important algorithms for bipartite graphs maximum matching are observed. These algorithms either find maximum matching in non-weighted bipartite graph (e.g. Hopcroft and Karp’s algorithm — ) or choose among all matchings with maximum size one having maximal cost (e.g. Edmonds and Karp’s algorithm-). Provided that, in praxis new target settings and algorithms for finding maximum matching in bipartite graphs are also desirable.
The purpose of the article is to consider a new task setting and algorithms for maximum matching in weighted bipartite graphs as well as using these algorithms in fingerprint recognition.
Methods. Modified versions of finding maximum matching M in graph by searching and augmentation of M-augmenting paths are used.
Results. Weighted bipartite graph with a cost function , that associates each edge with one of two possible values (e.g. 0 or 1) is considered. Maximum matching in the graph in new setting consists in finding among all matchings containing maximum number of edges with weight 1, one having maximal cardinality. Two algorithms with complexity being modified versions of the Hopcroft-Karp algorithm are proposed. Examples of using these algorithms for removing gaps of lines and finding true correspondence of minutiae in fingerprint recognition are considered.
Conclusions. Proposed algorithms find maximum matching in input bipartite graph among all matchings having maximal cardinality in given subset of this graph edges. Using of proposed algorithms leads to increasing processing speed and reliability of fingerprint recognition.
Key words: maximum matching, bipartite graph, images
REFERENCES
1 C. Berge. Two theorems in graph theory. In Proc. National Academy Sciences, USA. 1957. P. 842–844. https://doi.org/10.1073/pnas.43.9.842
2 J.A. Bondy and U.S.R. Murty. Graph theory wih applications. Mac Millan, New York, 1976. https://doi.org/10.1007/978-1-349-03521-2
3 T. Kim and K.Y. Chwa. An parallel maximum matching algorithm for bipartite graphs. Inf. Proc. Letters. 1987. 24(1), P.15–17. https://doi.org/10.1016/0020-0190(87)90193-1
4 4. Act, N.Blum, K. Mehlhorn, and M. Paul. Computing a maximum cardinality matching in a bipartite graph in time . Inf. Proc. Letters. 1991. 37, P. 237–240. https://doi.org/10.1016/0020-0190(91)90195-N
5 5. Hopcroft and R. Karp. An algorithm for maximum matching in bipartite graphs. SIAM Journal Comput. 1973. 2(4), P. 225–231. https://doi.org/10.1137/0202019
6 E.A. Dinic. Algorithm for solution of a problem of maximum flow in a network with power estimation. Soviet Math. Dokl. 1970. 11(5). P. 1277–1280.
7 H.W. Kuhn. The Hungarian method for the assignment problem. Naval Res. Logist., Quart. 1955. 2. P. 83–97.
8 H.W. Kuhn. Variants of the Hungarian method for the assignment problem. Naval Res. Logist., Quart. 1956. 3. P. 253–258.
9 J. Munkres. Algorithms for the assignment and transportation problems. J. Soc. Indust. Appl. Math. 1957, P. 32–38. https://doi.org/10.1137/0105003
10 J. Edmonds and R. Karp. Theoretical improvements in algorithmic efficiency for network flow problems. J. of the Assoc. for Comput. Mach. 1972. 19(2), P. 248–264. https://doi.org/10.1145/321694.321699
11 11. L. Fredman and R.E. Tarjan. Fibonacci heaps and their uses in imroved network optimization algorithms. In 25th FOCS. 1984. P. 338–346.
12 H.V. Gasparian, A.A. Kirakosian. The comparison system of fingerprints by local features. Vestnik of RAU, Natural Science, Physics and Mathematics. 2006. P. 85–91. (in Russian).
13 A.S. Rykanov. Analysis of fingerprint authentification and verification methods. Systems for information processing. 6(87). 2010. P. 164–181. (in Russian).
14 14. Chengfeng Wang, Marina Gavrilova, Yuan Luo and Jon Rokne. An efficient algorithm for fingerprint matching. ICPR. 1. 2006. P. 1034–
15 T. Cormen, C. Leiserson, R. Rivest and C. Stein. Introduction to algorithm. The MIT Press, 2002.
16 V.M. Kyyko, V.V. Matsello. Fingerprints recognition based on searching of corresponding points. Control systems and machines. No 3. 2005. P. 36–41 (in Russian).
17 R. Jonker R., A. Volgenant. A shortest augmenting path algorithm for dense and sparse linear assignment problems. Computing 38. 1987. P. 325–340. https://doi.org/10.1007/BF02278710
Received 24.11.2017