Maximum Matching in Regular and Almost Regular Graphs |
| |
Authors: | Raphael Yuster |
| |
Affiliation: | 1. Department of Mathematics, University of Haifa, Haifa, 31905, Israel
|
| |
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(\sqrt{n}m)$ -time for graphs with m edges, whenever m=ω(rn 1.5logn). |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|