AN EFFICIENT PARALLEL ALGORITHM FOR THE ASSIGNMENT PROBLEM ON THE PLANEFootnote∗

∗This research was supported by the Natural Sciences and Engineering Research Council of Canada under grant A3336.

References

• A. V. Aho , J. E. Hopcroft and J. D. Ullman , Data Structures and Algorithms. Addison-Wesley Publishing Company , Reading , MA , 1983 .
   Google Scholar
• A. V. Aho , J. E. Hopcroft and J. D. Ullman , The Design and Analysis of Computer Algorithms. Addison-Wesley Publishing , Reading , MA , 1974 .
   Google Scholar
• S. G. Akl , The Design and Analysis of Parallel Algorithms. Prentice Hall , Englewood Cliffs , NJ , 1989 .
   Google Scholar
• D. Avis , A survey of heuristics for the weighted matching problems , Networks 13 , 4 ( 1983 ), 475 – 493 .
   Web of Science ®Google Scholar
• D. Avis , Worst case bounds for the Euclidean matching problems , Computers and Mathematics with Applications 7 ( 1981 ), 251 – 257 .
   Google Scholar
• D. Avis , Two greedy heuristics for the weighted matching problem , Congressus Numerantium 19 ( 1978 ), 65 – 76 .
   Google Scholar
• J. J. Bartholdi , III and L. R. Platzman , A fast heuristic based on space filling curves for minimum-weight matching in the plane , Information Processing Letters 17 , 4 ( 1983 ), 177 – 180 .
   Web of Science ®Google Scholar
• R. P. Brent , The parallel evaluation of general arithmetic expressions , Journal of the Association for Computing Machinery 21 , 2 ( 1974 ), 201 – 206 .
   Web of Science ®Google Scholar
• V. Chvdtal , Linear Programming. W H. Redman and Company , New York , NY , 1983 .
   Google Scholar
• R. Cole and U. Vishkin , Approximate parallel scheduling. Part I The basic technique with applications to optimal list ranking in logarithmic time , SLAM Journal on Computing 17 , 1 ( 1988 ), 128 – 142 .
   Web of Science ®Google Scholar
• R. Cole and U. Vishkin , Approximate parallel and exact parallel scheduling with applications to lists, tree and graph problems . In Proceedings of the IEEE 27th Symposium on Foundations of Computer Science , IEEE , New York , , 1986 478 – 491 .
   Google Scholar
• J. R. Driscoll , H. N. Gabow , R. Shrairman and R. E. Tarjan , An alternative to fibonacci heaps with applications to parallel computation , Communications of the Association for Computing Machinery 31 , 11 ( 1988 ), 1343 – 1354 .
   Web of Science ®Google Scholar
• H. Edelsbrunner , L. J. Guibas and J. Stolfi , Optimal point location in monotone subdivision , SlAM Journal on Computing 15 , 2 ( 1986 ), 317 – 340 .
   Web of Science ®Google Scholar
• S. Fortune , A sweeplinc algorithm for Voronoi diagrams , Algorithmica 2 ( 1987 ), 153 – 174 .
   Web of Science ®Google Scholar
• M. L. Fredman and R. E. Tarjan , Fibonacci heaps and their uses in improved network optimization algorithms , Journal of the Association for Computing Machinery 34 , 3 ( 1987 ), 596 – 615 .
   Web of Science ®Google Scholar
• H. N. Gabow and R. E. Tarjan , Almost-optimum speed-ups of algorithms for bipartite matching and related problems , Proceedings of the 20th Annual ACM Symposium on Theory of Computing ACM , New York , May 2–4 , , 1988 514 – 527 .
   Google Scholar
• H. N. Gabow and R. E. Tarjan , Fast scaling algorithms for network problems . Technical Report No. CS-TR-111-87, Department of Computer Science , Princeton University , Princeton , NJ , August 1987 .
   Google Scholar
• Z. Galil , Sequential and parallel algorithm for finding maximum matching in graphs , Annual Review of Computer Science 1 ( 1986 ), 197 – 224 .
   Google Scholar
• Z. Galil , Efficient algorithms for finding maximum matching in graphs , Computing Surveys 18 , 1 ( 1986 ), 23 – 38 .
   Web of Science ®Google Scholar
• A. V. Goldberg , S. A. Plotkin and P. M. Vaidya , Sublinear-time parallel algorithms for matching and related problems . In Proceedings of the 29th Annual IEEE Symposium on Foundations of Computer Science , IEEE, New York, , 1988 174 – 185 .
   Google Scholar
• M. D. Grigoriadis and B. Kalantari , A new class of heuristic algorithms for weighted perfect matching , Journal of the Association for Computing Machinery 35 , 4 ( 1988 ), 769 – 776 .
   Web of Science ®Google Scholar
• M. D. Grigoriadis , B. Kalantari , A lower bound to the complexity of Euclidean and rectilinear matching algorithms , Information Processing Letters 22 ( 1986 ), 73 – 76 .
   Google Scholar
• M. Iri , K. Murota and S. Matsui , Heuristics for planar minimum-weight perfect matchings , Networks 13 , 1 ( 1983 ), 67 – 92 .
   Web of Science ®Google Scholar
• M. Iri , K. Murota and S. Matsui , Linear-time approximation algorithms for finding the minimum-weight perfect matching in the plane , Information Processing Letters 12 , 4 ( 1981 ), 206 – 209 .
   Web of Science ®Google Scholar
• C. P. Kruskal , L. Rudolph and M. Snir , Efficient parallel algorithms for graph problems , Algorith-mica 5 ( 1990 ), 43 – 64 .
   Web of Science ®Google Scholar
• H. W. Kuhn , The Hungarian method for the assignment problem , Naval Research Logistics Quarterly 2 ( 1955 ), 83 – 87 .
   Google Scholar
• E. L. Lawlcr , Combinatorial Optimization Networks and Matroids. Holt-Rinehart-Winston , New York , 1976 .
   Google Scholar
• D. T. Lcc and E P. Preparata , Location of a point in a planar subdivision and its applications , SIAM Journal on Computing 6 , 3 ( 1977 ), 594 – 606 .
   Google Scholar
• K. Mehlhorn , Data Structures and Algorithms 3 Multi-dimensional Searching and Computational Geometry , EATCS Monograph on Theoretical Computer Science ( W. Brauer, G. Rozenbcrg and A. Salomaa, eds. ), Springer-Verlag , New York , 1984 .
   Google Scholar
• K. Mchlhorn , Lower bounds on the efficiency of transforming static data structures into dynamic data structures , Mathematical Systems Theory 15 ( 1981 ), 1 – 16 .
   Google Scholar
• K. Mehlhorn and M. H. Overmars , Optimal dynamization of decomposable search problems , Information Processing Letters 12 , 2 ( 1981 ), 93 – 98 .
   Web of Science ®Google Scholar
• C. N. K. Osiakwan and S. G. Aid , Parallel computation of matchings in trees , Parallel Computing 17 , 6–7 ( 1991 ), 643 – 656 .
   Web of Science ®Google Scholar
• C. N. K. Osiakwan and S. G. Akl , The maximum weight perfect matching problem for complete weighted graphs is in PC* . In Proceedings of the Second Symposium on Parallel and Distributed Computing , Dallas , TX , December 9–13 , , 1990 pp. 880 – 887 .
   Google Scholar
• C. N. K. Osiakwan and S. G. Akl , A perfect speedup parallel algorithm for the assignment problem on complete weighted bipartite graphs ( N. Rishe, S. Navathe and D. Tal, cds. ), Parallel Architectures , IEEE Computer Society Press , Los Alamitos , CA , 161 – 180 .
   Google Scholar
• M. H. Overmars , J. van Leeuwcn , Worst-case optimal insertion and deletion methods for decomposable search problems , Information Processing Letters 12 , 4 ( 1981 ), 168 – 173 .
   Web of Science ®Google Scholar
• M. H. Overmars , J. van Leeuwen , Some principles for dynamizing decomposable searching problems , Information Processing Letters 12 , 1 ( 1981 ), 49 – 54 .
   Web of Science ®Google Scholar
• D. A. Plaisted , Heuristic matching for graphs satisfying the triangle inequality , Journal of Algorithms 5 ( 1984 ), 163 – 179 .
   Google Scholar
• F. P. Preparata and M. I. Shamos , Computational Geometry An Introduction. Springer-Verlag , New York Inc. , 1985 .
   Google Scholar
• E. M. Reingold and K. J. Supowit , Probabilistic analysis of divid-and-conquer heuristics for minimum weighted Euclidean matching , Networks 13 , 1 ( 1983 ), 49 – 66 .
   Web of Science ®Google Scholar
• E. M. Reingold and R. E. Tarjan , On a greedy heuristic for complete matching , SIAM Journal on Computing 10 , 4 ( November 1981 ), 676 – 681 .
   Web of Science ®Google Scholar
• M. Sharir , Closest-pair problems for a set of planar discs , SIAM Journal on Computing 14 , 2 ( May 1985 ), 448 – 468 .
   Web of Science ®Google Scholar
• K. J. Supowit , New techniques for some dynamic closest-point and farthest-point problems , Proceedings of the 1st Annual ACM-SIAM Symposium on Discrete Algorithms , San Francisco , CA , January 22–24 , , 1990 84 – 90 .
   Google Scholar
• K. J. Supowit and E. M. Reingold , Dividc-and-conqucr heuristic for minimum weighted Euclidean matching , SIAM Journal on Computing 12 , 1 ( 1983 ), 118 – 143 .
   Web of Science ®Google Scholar
• K. J. Supowit , e. M, Reingold and D. A. Plaisted , The traveling salesman problem and minimum matching in the unit square , SIAM Journal on Computing 12 , 1 ( 1983 ), 144 – 156 .
   Web of Science ®Google Scholar
• K. J. Supowit , D. A. Plaisted and E. M. Reingold , Heuristics for weighted perfect matching , Proceedings of the I2tlt Annual ACM Symposium on Theory of Computing Science , Los Angeles , CA , April 28-30 , , 1980 398 – 419 .
   Google Scholar
• R. E. Tarjan , Data Structures and Network Algorithms , Society for Industrial and Applied Mathematics , Philadelphia , PA , 1983 .
   Google Scholar
• P. M. Vaidya , Geometry helps in matching , SIAM Journal on Computing 18 , 6 ( Dec. 1989 ), 1201 – 1225 .
   Web of Science ®Google Scholar
• ∗This research was supported by the Natural Sciences and Engineering Research Council of Canada under grant A3336.
   Google Scholar