|
 ABSTRACT
Megiddo introduced a technique for using a parallel algorithm for one problem to construct an efficient serial algorithm for a second problem. This paper provides a general method that trims a factor of O(log n) time (or more) for many applications of this technique.
REFERENCES
Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.
| |
1
|
|
| |
2
|
|
| |
3
|
COLE, R., AND YAP, C. A parallel median algorithm. Inf. Process. Lett. 20 (1985), 137-139.
|
| |
4
|
|
| |
5
|
FREDERICKSON, G., AND JOHNSON, D. Finding k-th paths and p-centers by generating and searching good data structures. ~ Algorithms 4 (1983), 61-80.
|
| |
6
|
GABBER, O., AND GALIL, Z. Explicit construction of linear size superconcentrators. ~ Comput. Syst. Sci. 22 (1981), 407-420.
|
| |
7
|
GABOW, H., GALIL, Z., AND SPENCER, T. Efficient implementation of graph algorithms using contraction. In Proceedings of the 25th Annual Symposium on the Foundations of Computer Science. IEEE, New York, 1984, 347-357.
|
| |
8
|
MEGIDDO, N. Combinatorial optimization with rational objective functions. Math. Oper. Res. 4 (1979), 414-424.
|
 |
9
|
|
| |
10
|
MEGIDDO, N. Linear time algorithms for linear programming in R3 and related problems. SIAM ~ Comput. 12 (1983), 759-776.
|
| |
11
|
MEGIDDO, N. Partitioning with two lines in the plane. ~ Algorithms 6 (1985), 430-433.
|
| |
12
|
MEGIDDO, N., AND TAMIR, A. New results on the complexity of p-center problems. SIAM J. Comput. 12, 4 (1983), 751-758.
|
| |
13
|
PREPARATA, F. New parallel sorting schemes. IEEE Trans. Comput. C-27 (1978), 669-673.
|
| |
14
|
REISCHUK, R. A fast probabilistic sorting algorithm. In Proceedings of the 22nd Annual Symposium on the Foundations of Computer Science. IEEE, New York, 1981, 212-219.
|
| |
15
|
REISER, A. A linear selection algorithm for sets of elements with weights. Inf. Process. Lett. 7 (1978), 159-162.
|
| |
15a
|
SHILOACH, Y., AND VISHKIN, O. Finding the maximum, merging and sorting in a parallel computation model. J. Algorithms 2 ( 1981), 88-102.
|
| |
16
|
VALIANT, L. Parallelism in comparison problems. SIAM J. Comput. 4 (1975), 348-355.
|
CITED BY 57
|
|
|
|
|
|
|
|
Bernard Chazelle , Herbert Edelsbrunner , Leonidas Guibas , Micha Sharir, Diameter, width, closest line pair, and parametric searching, Proceedings of the eighth annual symposium on Computational geometry, p.120-129, June 10-12, 1992, Berlin, Germany
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Dan Halperin , Micha Sharir , Ken Goldberg, The 2-center problem with obstacles, Proceedings of the sixteenth annual symposium on Computational geometry, p.80-90, June 12-14, 2000, Clear Water Bay, Kowloon, Hong Kong
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Alok Aggarwal , Baruch Schieber , Takashi Tokuyama, Finding a minimum weight K-link path in graphs with Monge property and applications, Proceedings of the ninth annual symposium on Computational geometry, p.189-197, May 18-21, 1993, San Diego, California, United States
|
|
|
Christian A. Duncan , Michael T. Goodrich , Edgar A. Ramos, Efficient approximation and optimization algorithms for computational metrology, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.121-130, January 05-07, 1997, New Orleans, Louisiana, United States
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Pankaj K. Agarwal , Sergey Bereg , Ovidiu Daescu , Haim Kaplan , Simeon Ntafos , Binhai Zhu, Guarding a terrain by two watchtowers, Proceedings of the twenty-first annual symposium on Computational geometry, June 06-08, 2005, Pisa, Italy
|
|
|
|
|
|
|
|
|
Pankaj K. Agarwal , Boris Aronov , Micha Sharir , Subhash Suri, Selecting distances in the plane, Proceedings of the sixth annual symposium on Computational geometry, p.321-331, June 07-09, 1990, Berkley, California, United States
|
|
|
|
|
|
Erin Wolf Chambers , Éric Colin de Verdière , Jeff Erickson , Sylvain Lazard , Francis Lazarus , Shripad Thite, Walking your dog in the woods in polynomial time, Proceedings of the twenty-fourth annual symposium on Computational geometry, June 09-11, 2008, College Park, MD, USA
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Timothy G. Abbott , Michael A. Burr , Timothy M. Chan , Erik D. Demaine , Martin L. Demaine , John Hugg , Daniel Kane , Stefan Langerman , Jelani Nelson , Eynat Rafalin , Kathryn Seyboth , Vincent Yeung, Dynamic ham-sandwich cuts in the plane, Computational Geometry: Theory and Applications, v.42 n.5, p.419-428, July, 2009
|
REVIEW
"Daniel P. Bovet : Reviewer"
As clearly stated by the author, the paper presents an “improvement of
Megiddo's ingenious technique [1], which uses an efficient parallel algorithm
for one problem to produce an efficient serial algorithm for a second
problem.” In o
more...
|
Adobe Acrobat
QuickTime
Windows Media Player
Real Player
Pdf
G.1