Maximum Matching in Weighted Bipartite Graphs

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...

Повний опис

Збережено в:
Бібліографічні деталі
Дата: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 назв. — англ.

Репозитарії

Digital Library of Periodicals of National Academy of Sciences of Ukraine
id irk-123456789-131936
record_format dspace
spelling irk-123456789-1319362018-09-25T16:57:39Z Maximum Matching in Weighted Bipartite Graphs Kyyko, V.M. Информатика и информационные технологии 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). Розглянуто приклади вживання цих алгоритмів для усунення розривів ліній та пошуку відповідності особливих точок на порівнюваних відбитках пальців при розв’язанні задачі розпізнавання папілярних зображень. Висновки. Запропоновано нові алгоритми пошуку найбільшого паросполучення на зваженому дводольному графові. Використання запропонованих алгоритмів призводить до пришвидчення та зростання надійності розпізнавання зображень відбитків пальців. 2018 Article 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 http://dspace.nbuv.gov.ua/handle/123456789/131936 519.1 en Кибернетика и вычислительная техника Міжнародний науково-навчальний центр інформаційних технологій і систем НАН України та МОН України
institution Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection DSpace DC
language English
topic Информатика и информационные технологии
Информатика и информационные технологии
spellingShingle Информатика и информационные технологии
Информатика и информационные технологии
Kyyko, V.M.
Maximum Matching in Weighted Bipartite Graphs
Кибернетика и вычислительная техника
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.
format Article
author Kyyko, V.M.
author_facet Kyyko, V.M.
author_sort Kyyko, V.M.
title Maximum Matching in Weighted Bipartite Graphs
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
publisher Міжнародний науково-навчальний центр інформаційних технологій і систем НАН України та МОН України
publishDate 2018
topic_facet Информатика и информационные технологии
url http://dspace.nbuv.gov.ua/handle/123456789/131936
citation_txt Maximum Matching in Weighted Bipartite Graphs / V.M. Kyyko // Кибернетика и вычисл. техника. — 2018. — № 1 (191). — С. 32-44. — Бібліогр.: 17 назв. — англ.
series Кибернетика и вычислительная техника
work_keys_str_mv AT kyykovm maximummatchinginweightedbipartitegraphs
first_indexed 2023-10-18T21:03:18Z
last_indexed 2023-10-18T21:03:18Z
_version_ 1796151805197942784

Схожі ресурси