|
|||||
|
|
The general maximum matching algorithm of micali and vazirani |
|
| Authors: | Paul A Peterson and Michael C Loui |
| Affiliation: | (1) Department of Electrical and Computer Engineering and Coordinated Science Laboratory, University of Illinois at Urbana-Champaign, 61801 Urbana, IL, USA;(2) Present address: NCR Corporation, 1601 South Main Street, 45479 Dayton, OH, USA |
| Abstract: | We give a clear exposition of the algorithm of Micali and Vazirani for computing a maximum matching in a general graph. This is the most efficient algorithm known for general matching. On a graph withn vertices andm edges this algorithm runs inO(n 1/2 m) time.Work on this paper has been supported by the Office of Naval Research under Contract N00014-85-K-0570 and by the Eastman Kodak Company. |
| Keywords: | Matching Graph algorithm Combinatorial optimization |
| 本文献已被 SpringerLink 等数据库收录！ | |