ANSI-C 1994-1996

Quasi-Convex Matching Software

S. R. Buss, and K. G. Kanzelberger, and D. R. Robinson, and P. N. Yianilos

Description: This software implements the near linear time algorithms of Buss and Yianilos for solving a special class of bipartite weighted matching problems (assignment). Their paper "Linear and O(n log n) Time Minimum-Cost Matching Algorithms for Quasi-convex Tours" appeared in SODA94, and will appear in Siam J. Computing.

The software was first described in UCSD Technical Report CS94-370 entitled "Solving the Minimum-Cost Matching Problem for Quasi-Convex Tours: An Efficient ANSI C Implementation", by the four authors above.


After its initial release in 1994, this software has been only slightly modified.