Maximum Matching in Weighted Bipartite Graphs

• Дата: 2018
• Автор: Kyyko, V.M.
• Формат: Стаття
• Мова: English
• Опубліковано: Міжнародний науково-навчальний центр інформаційних технологій і систем НАН України та МОН України 2018
• Назва видання: Кибернетика и вычислительная техника
• Теми: Информатика и информационные технологии
• Онлайн доступ: http://dspace.nbuv.gov.ua/handle/123456789/131936
• Назва журналу: Digital Library of Periodicals of National Academy of Sciences of Ukraine
• Цитувати: Maximum Matching in Weighted Bipartite Graphs / V.M. Kyyko // Кибернетика и вычисл. техника. — 2018. — № 1 (191). — С. 32-44. — Бібліогр.: 17 назв. — англ.

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 G = (V ,E ) with a cost function ce : E → { 0,1} , 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 O(m√n ) 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.