zbMATH — the first resource for mathematics

Heuristics for planar minimum-weight perfect matchings. (English) Zbl 0503.68050

68R10 Graph theory (including graph drawing) in computer science
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
Full Text: DOI
[1] , and , The Design and Analysis of Computer Algorithms. Addison-Wesley, Reading, Ma. (1974).
[2] Iri, Information Processing Lett. 12 pp 206– (1981)
[3] , and , An approximate solution for the problem of optimizing the plotter pen movement. In Proc. 10th IFIP Conference on System Modeling and Optimization Lecture Notes in Control and Information Sciences, 38, and , Eds. Springer-Verlag, New York (1982) 572–580.
[4] , and , Linear-time heuristics for the minimum-weight perfect matching on a plane with an application to the plotter algorithm. Research Memorandum RMI 81–07. Department of Mathematical Engineering and Instrumentation Physics, University of Tokyo (1981).
[5] and , The determination of the pen-movement of an X Y-plotter and its computational complexity (in Japanese). In Proc. Spring Conference of the Operations Research Society of Japan, P–8, 1980, pp. 204, 205.
[6] Combinatorial Optimization-Networks and Matroids. Holt, Rine-hart and Winston, New York (1976).
[7] The probabilistic analysis of matching heuristics. In Proc. 15th Ann. Allerton Conf. on Communication, Control and Computing, 1977, pp. 368–378.
[8] Reingold, SIAM J. Comput. 10 pp 676– (1981)
[9] Subadditive Euclidean functional and non-linear growth in geometric probability. Ann. of Probability 9 (1981) 365–376. · Zbl 0461.60029
[10] , and , Heuristics for weighted perfect matching. In Proc. 12th Ann. ACM Symp. on Theory of Computing, 1980, pp. 398–414.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.