Guo-Jun Qi, Charu Aggarwal, et al.
IEEE TPAMI
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.
Guo-Jun Qi, Charu Aggarwal, et al.
IEEE TPAMI
Salvatore Certo, Anh Pham, et al.
Quantum Machine Intelligence
Timothy J. Wiltshire, Joseph P. Kirk, et al.
SPIE Advanced Lithography 1998
John S. Lew
Mathematical Biosciences