Heuristics for planar minimum‐weight perfect metchings
Masao Iri, Kazuo Murota, Shouichi Matsui · Networks · 1983
Abstract Several linear‐time approximation algorithms for the minimum‐weight perfect matching in a plane are proposed, and their worst‐ and average‐case behaviors are analyzed theoretically as well as experimentally. A linear‐time approximation algorithm, named the “spiral‐rack algorithm (with preprocess and with tour),” is recommended for practical purposes. This algorithm is successfully applied to the drawing of road maps such as that of the Tokyo city area.