Maximum Matching in Weighted Bipartite Graphs
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...
Saved in:
| Published in: | Кибернетика и вычислительная техника |
|---|---|
| Date: | 2018 |
| Main Author: | |
| Format: | Article |
| Language: | English |
| Published: |
Міжнародний науково-навчальний центр інформаційних технологій і систем НАН України та МОН України
2018
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/131936 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Maximum Matching in Weighted Bipartite Graphs / V.M. Kyyko // Кибернетика и вычисл. техника. — 2018. — № 1 (191). — С. 32-44. — Бібліогр.: 17 назв. — англ. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-131936 |
|---|---|
| record_format |
dspace |
| spelling |
Kyyko, V.M. 2018-04-06T20:29:29Z 2018-04-06T20:29:29Z 2018 Maximum Matching in Weighted Bipartite Graphs / V.M. Kyyko // Кибернетика и вычисл. техника. — 2018. — № 1 (191). — С. 32-44. — Бібліогр.: 17 назв. — англ. 0454-9910 DOI: doi.org/10.15407/kvt191.01.032 https://nasplib.isofts.kiev.ua/handle/123456789/131936 519.1 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. Рассмотрена новая постановка задачи нахождения наибольшего паросочетания на взвешенном двудольном графе, веса ребер которого принимают два значения (например, 0 и 1): найти все паросочетания, содержащие наибольшее количество ребер с весом 1, и выбрать среди них наибольшее по размеру паросочетание. Предложены два алгоритма поиска наибольшего паросочетания на двудольном графе в новой постановке со сложностью O(m√n) . Рассмотрены примеры применения этих алгоритмов для устранения разрывов линий и поиска соответствия особых точек на двух сравниваемых отпечатках пальцев при решении задачи распознавания папиллярных изображений. Мета статті — розглянути нові постановки завдання щодо знаходження найбільшого паросполучення на зваженому дводольному графові, алгоритми розв’язання цієї задачі, а також використання цих алгоритмів при розпізнаванні папілярних зображень. Методи. Використовуються модифіковані версії пошуку найбільшого паросполучення M на дводольному графові на основі пошуку та аугментації M - збільшуючих шляхів на цьому графові. Результати. Розглянуто нову постановку пошуку найбільшого паросполучення на зваженому дводольному графові, ваги ребер якого набувають два значення (наприклад, 0 і 1): знайти всі паросполучення, що мають найбільшу кількість ребер з вагою 1, і вибрати серед них таке паросполучення, що має найбільшу кількість ребер. Запропоновано два алгоритми пошуку найбільшого паросполучення у цій постановці зі складністю O(m√n). Розглянуто приклади вживання цих алгоритмів для усунення розривів ліній та пошуку відповідності особливих точок на порівнюваних відбитках пальців при розв’язанні задачі розпізнавання папілярних зображень. Висновки. Запропоновано нові алгоритми пошуку найбільшого паросполучення на зваженому дводольному графові. Використання запропонованих алгоритмів призводить до пришвидчення та зростання надійності розпізнавання зображень відбитків пальців. en Міжнародний науково-навчальний центр інформаційних технологій і систем НАН України та МОН України Кибернетика и вычислительная техника Информатика и информационные технологии Maximum Matching in Weighted Bipartite Graphs Нахождение наибольшего паросочетания на взвешенном двудольном графе Знаходження найбільшого паросполучення на зваженому дводольному графові Article published earlier |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| title |
Maximum Matching in Weighted Bipartite Graphs |
| spellingShingle |
Maximum Matching in Weighted Bipartite Graphs Kyyko, V.M. Информатика и информационные технологии |
| title_short |
Maximum Matching in Weighted Bipartite Graphs |
| title_full |
Maximum Matching in Weighted Bipartite Graphs |
| title_fullStr |
Maximum Matching in Weighted Bipartite Graphs |
| title_full_unstemmed |
Maximum Matching in Weighted Bipartite Graphs |
| title_sort |
maximum matching in weighted bipartite graphs |
| author |
Kyyko, V.M. |
| author_facet |
Kyyko, V.M. |
| topic |
Информатика и информационные технологии |
| topic_facet |
Информатика и информационные технологии |
| publishDate |
2018 |
| language |
English |
| container_title |
Кибернетика и вычислительная техника |
| publisher |
Міжнародний науково-навчальний центр інформаційних технологій і систем НАН України та МОН України |
| format |
Article |
| title_alt |
Нахождение наибольшего паросочетания на взвешенном двудольном графе Знаходження найбільшого паросполучення на зваженому дводольному графові |
| description |
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.
Рассмотрена новая постановка задачи нахождения наибольшего паросочетания на взвешенном двудольном графе, веса ребер которого принимают два значения (например, 0 и 1): найти все паросочетания, содержащие наибольшее количество ребер с весом 1, и выбрать среди них наибольшее по размеру паросочетание. Предложены два алгоритма поиска наибольшего паросочетания на двудольном графе в новой постановке со сложностью O(m√n) . Рассмотрены примеры применения этих алгоритмов для устранения разрывов линий и поиска соответствия особых точек на двух сравниваемых отпечатках пальцев при решении задачи распознавания папиллярных изображений.
Мета статті — розглянути нові постановки завдання щодо знаходження найбільшого паросполучення на зваженому дводольному графові, алгоритми розв’язання цієї задачі, а також використання цих алгоритмів при розпізнаванні папілярних зображень. Методи. Використовуються модифіковані версії пошуку найбільшого паросполучення M на дводольному графові на основі пошуку та аугментації M - збільшуючих шляхів на цьому графові. Результати. Розглянуто нову постановку пошуку найбільшого паросполучення на зваженому дводольному графові, ваги ребер якого набувають два значення (наприклад, 0 і 1): знайти всі паросполучення, що мають найбільшу кількість ребер з вагою 1, і вибрати серед них таке паросполучення, що має найбільшу кількість ребер. Запропоновано два алгоритми пошуку найбільшого паросполучення у цій постановці зі складністю O(m√n). Розглянуто приклади вживання цих алгоритмів для усунення розривів ліній та пошуку відповідності особливих точок на порівнюваних відбитках пальців при розв’язанні задачі розпізнавання папілярних зображень. Висновки. Запропоновано нові алгоритми пошуку найбільшого паросполучення на зваженому дводольному графові. Використання запропонованих алгоритмів призводить до пришвидчення та зростання надійності розпізнавання зображень відбитків пальців.
|
| issn |
0454-9910 |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/131936 |
| citation_txt |
Maximum Matching in Weighted Bipartite Graphs / V.M. Kyyko // Кибернетика и вычисл. техника. — 2018. — № 1 (191). — С. 32-44. — Бібліогр.: 17 назв. — англ. |
| work_keys_str_mv |
AT kyykovm maximummatchinginweightedbipartitegraphs AT kyykovm nahoždenienaibolʹšegoparosočetaniânavzvešennomdvudolʹnomgrafe AT kyykovm znahodžennânaibílʹšogoparospolučennânazvaženomudvodolʹnomugrafoví |
| first_indexed |
2025-12-07T16:26:18Z |
| last_indexed |
2025-12-07T16:26:18Z |
| _version_ |
1850867479801233408 |