Search Paper
  • Home
  • Login
  • Categories
  • Post URL
  • Academic Resources
  • Contact Us

 

A DFS Algorithm for Maximum Matchings in General Graphs

google+
Views: 27                 

Author :  Tony T. Lee, Bojun Lu and Hanli Chu

Affiliation :  The Chinese University of Hong Kong

Country :  China

Category :  Computer Science & Information Technology

Volume, Issue, Month, Year :  13, 03, February, 2023

Abstract :


In this paper, we propose a depth-first search (DFS) algorithm for finding maximum matching in general graphs. Unlike blossom shrinking algorithms, which store all possible alternative alternating-paths in the super-vertices shrinking 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 the 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 𝑂(𝑚𝑛) time with space complexity 𝑂(𝑛).

Keyword :  Maximum Matching, Augmenting Path, Blossom, Trunk, Sprout.

Journal/ Proceedings Name :  computer science&information technology

URL :  https://csitcp.org/abstract/13/133csit10

User Name : alex
Posted 20-05-2023 on 14:05:41 AEDT



Related Research Work

  • Development Of A Monitoring System For The Management Of Medical Devices
  • University Buses Routing And Tracking System
  • Eye-tracking In Association With Phishing Cyber Attacks: A Comprehensive Literature Review
  • An Integrative App Producing An Optimal Path For The Vessel In Order To Reduce The Impacts Of Cargo Ships On The Environment

About Us | Post Cfp | Share URL Main | Share URL category | Post URL
All Rights Reserved @ Call for Papers - Conference & Journals