A DFS Algorithm for Maximum Matchings in General Graphs

Autor:	Tony T. Lee, Bojun Lu, Hanli Chu
Rok vydání:	2022
Předmět:	FOS: Computer and information sciences 05C30 (Primary) 68R10 68R05 (Secondary) Computer Science - Data Structures and Algorithms G.2.1 Data Structures and Algorithms (cs.DS) G.2.2 F.2.2 MathematicsofComputing_DISCRETEMATHEMATICS
DOI:	10.48550/arxiv.2201.12811
Popis:	In this paper, we propose a depth-first search (DFS) algorithm for searching maximum matchings in general graphs. Unlike blossom shrinking algorithms, which store all possible alternative alternating paths in the super-vertices shrunk from blossoms, the newly proposed algorithm does not involve blossom shrinking. The basic idea is to deflect the alternating path when facing blossoms. The algorithm maintains detour information in an auxiliary stack to minimize the redundant data structures. A benefit of our technique is to avoid spending time on shrinking and expanding blossoms. This DFS algorithm can determine a maximum matching of a general graph with $m$ edges and $n$ vertices in $O(mn)$ time with space complexity $O(n)$. Comment: 17 pages, 9 figures, 2 tables
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_dedup___::21ff0a551c9250a91a0c7ea677305dab Zobrazit plný text záznamu