johnk@cs.arizona.edu (John Kececioglu) (01/09/90)
I wish to thank Hershel Safer, Bruce Smith, Jon Turner, Robert Eachus, Thomas Spencer, and Constantine Osiakwan for generously responding to my article requesting algorithms for maximum weight matchings in nonbipartite graphs. Although I didn't make it clear in the original article, I wasn't interested in scaling algorithms. The following well-known references seem to cover the published sequential algorithms: Zvi Galil, "Efficient algorithms for finding maximum matchings in graphs," Computing Surveys 18:1 (March 1986) 23-38. Zvi Galil, Silvio Micali, and Harol Gabow, "An O(E V log V) algorithm for finding a maximal weighted matching in general graphs," SIAM J. Computing 15:1 (February 1986) 120-130. Harold Gabow, Zvi Galil, and Thomas Spencer, "Efficient implementation of graph algorithms using contraction," JACM 36:3 (July 1989) 540-572. The survey of Galil is excellent. The algorithm of Gabow, Galil, and Spencer achieves time O(V^2 log V + E V log log (log V / log(E/V))). Apparently, Gabow has designed a new algorithm to be presented at the Symposium on Discrete Algorithm (SODA) this month, with a running time of O(V^2 log V + EV). With regard to generating matchings in order, I knew only of the following reference, though I have not read the paper: K.G. Murty, "An algorithm for ranking all the assignments in increasing order of cost," Oper. Res. 16 (1968) 682-687. I received no response regarding which algorithm leads to a fast implementation. The algorithm of Galil, Micali, and Gabow looks reasonable, though it does appear that few of the algorithms designed have ever been implemented. If true, this seems rather unfortunate. -- John Kececioglu johnk@cs.arizona.edu or arizona!johnk.uucp Department of Computer Science, University of Arizona, Tucson, Arizona 85721 "Through small apertures we glimpse abysses whose somber depths turn us faint."