Maximum Matching in Regular and Almost Regular Graphs

Maximum Matching in Regular and Almost Regular Graphs

0.00 Avg rating0 Votes
Article ID: iaor20132082
Volume: 66
Issue: 1
Start Page Number: 87
End Page Number: 92
Publication Date: May 2013
Journal: Algorithmica
Authors:
Keywords: combinatorial optimization
Abstract:

We present an O(n 2logn)‐time algorithm that finds a maximum matching in a regular graph with n vertices. More generally, the algorithm runs in O(rn 2logn) time if the difference between the maximum degree and the minimum degree is less than r. This running time is faster than applying the fastest known general matching algorithm that runs in O ( n m ) equ1 ‐time for graphs with m edges, whenever m=ω(rn 1.5logn).

Reviews

Required fields are marked *. Your email address will not be published.