fry@brauer.harvard.edu (DSF2) (04/08/90)
Thanks to everyone for help in find an efficient algorithm to solve the maximum weight matching problem for complete bipartite graphs. For those interested, I was directed to such works as M.D. Plummer's "Matching Theory," Bondy and Murty's "Graph Theory with Applications," Lawler's "Combinatorial Optimization: Networks and Matroids," and various journals. Those dealt with my original question, the Hungarian algorithm. But I was also directed (thanks jh04@gte.com) to a recent paper by Jonker and Volgenant [Computing 38 (1987), pp. 325-40] that apparently defines the current state-of-the-art for this problem. Using the Pascal source included in the paper, I've experienced order-of- magnitudes improvement over my old routine. Thanks again to all. David Fry fry@huma1.harvard.EDU Department of Mathematics fry@huma1.bitnet Harvard University ...!harvard!huma1!fry Cambridge, MA 02138