Premium
Heuristics for planar minimum‐weight perfect metchings
Author(s) -
Iri Masao,
Murota Kazuo,
Matsui Shouichi
Publication year - 1983
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230130105
Subject(s) - heuristics , spiral (railway) , matching (statistics) , mathematical optimization , planar , algorithm , minimum weight , plane (geometry) , computer science , approximation algorithm , rack , mathematics , combinatorics , geometry , statistics , political science , law , computer graphics (images) , mathematical analysis
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.