🚀 go-pugleaf

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."