A.R. Conn, Nick Gould, et al.
Mathematics of Computation
We describe a new heuristic for constructing a minimum-cost perfect matching designed for problems on complete graphs whose cost functions satisfy the triangle inequality (e.g., Euclidean problems). The running time for an n node problem is O(n log n) after a minimum-cost spanning tree is constructed. We also describe a procedure which, added to Kruskal's algorithm, produces a lower bound on the size of any perfect matching. This bound is based on a dual problem which has the following geometric interpretation for Euclidean problems: Pack nonoverlapping disks centered at the nodes and moats surrounding odd sets of nodes so as to maximize the sum of the disk radii and moat widths. © 1995 Springer-Verlag New York Inc.
A.R. Conn, Nick Gould, et al.
Mathematics of Computation
Michael E. Henderson
International Journal of Bifurcation and Chaos in Applied Sciences and Engineering
Guo-Jun Qi, Charu Aggarwal, et al.
IEEE TPAMI
Zhihua Xiong, Yixin Xu, et al.
International Journal of Modelling, Identification and Control