R. Cypher and C. G. Plaxton. Deterministic sorting in nearly logarithmic time on the hypercube and related computers. A CM Symposium on Theory of Computing, 193-203. ACM, 1990.

Digital Library

Google Scholar

[6]

Grand Challenges: High Performance Computing a'nd Communications. The FY 1992 U.S. Research and Development. Program. A Report by the Committee on Physical, Mathematical, and Engineering Sciences. Federal Council for Science, Engineering, and Technology. To Supplement the U.S. President's Fiscal Year 1992 Budget.

Google Scholar

[7]

R. I. Greenberg and C. E. Leiserson. Randomized Routing on Fat-trees. Advances in Computing Research, 5:345-374, 1989.

Google Scholar

[8]

F. Dehne and J.-R. Sack. Translation separability of sets of polygons. The Visual Computer .3: 227-235, 1987.

Google Scholar

[9]

F. Dehne and A. Fabri and A. Rau-Chaplin. Data structure decomposition./'or Coarse Grained Multicomputers. Manuscript.

Google Scholar

[10]

S. Hart and M. Sharir. Nonlinearity of Davenport- Schinzel sequences and of generalized path compression schemes. Combinatorica, 6:151-177, 1986.

Digital Library

Google Scholar

[11]

J. Hershberger Finding the upper envelope of n line segments i'n O(nlog n) time Inf. Proc. Letters 33, 169- 174, 1989.

Digital Library

Google Scholar

[12]

F.T. Leighton. Introduction to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes. Morgan I(aufmann Publishers, San Mateo, CA, 1992.

Digital Library

Google Scholar

[13]

M. H. Overmars and J. van Leeuwen. Maintenance of configurations in the plane. J. Comput. Syst. Sci. 23:166-2(.t4, 1981.

Crossref

Google Scholar

[14]

F. P. Preparata and M. I. Shamos. Computational Geometry: an Introduction. Springer-Verlag, New York, NY, 1985.

Digital Library

Google Scholar

[15]

J. H. Reif and L. G. Valiant. A logarithmic time sort for linear size networks. J. A CM, Vol.34, 1:60-76, 1987.

Digital Library

Google Scholar

[16]

J. van Leeuwen and D. Wood. The measure problem for rectangular ranges in d-space. J. Algorithms, 2:282-300, 1981.

Crossref

Google Scholar

Cited By

View all

Bogning Tepiele HKengne Tchendji VAkong Onabid MMyoupo JNkonjoh Ngomade A(2024)Dominant Point-Based Sequential and Parallel Algorithms for the Multiple Sequential Substring Constrained-LCS ProblemACM Transactions on Parallel Computing10.1145/369665711:4(1-31)Online publication date: 23-Sep-2024
https://dl.acm.org/doi/10.1145/3696657
Nanfack ALe Mahec GDequen G(2024)Optimizing Privacy While Limiting Information Loss in Distributed Data Anonymization2024 IEEE International Conference on Big Data (BigData)10.1109/BigData62323.2024.10825321(352-359)Online publication date: 15-Dec-2024
https://doi.org/10.1109/BigData62323.2024.10825321
Lacmou Zeutouo JKengne Tchendji VMyoupo J(2022)Four-splitting based coarse-grained multicomputer parallel algorithm for the optimal binary search tree problemInternational Journal of Parallel, Emergent and Distributed Systems10.1080/17445760.2022.210216837:6(659-679)Online publication date: 28-Jul-2022
https://doi.org/10.1080/17445760.2022.2102168
Show More Cited By

Index Terms

Scalable parallel geometric algorithms for coarse grained multicomputers
1. Computer systems organization
  1. Architectures
    1. Parallel architectures
      1. Multiple instruction, multiple data
2. Theory of computation

Recommendations

Solving large graph problems on coarse-grained multicomputers
Efficient External Memory Algorithms by Simulating Coarse-Grained Parallel Algorithms

External memory (EM) algorithms are designed for large-scale computational problems in which the size of the internal memory of the computer is only a small fraction of the problem size. Typical EM algorithms are specially crafted for the EM situation. ...
Coarse grained parallel algorithms for graph matching

Parallel graph algorithm design is a very well studied topic. Many results have been presented for the PRAM model. However, these algorithms are inherently fine grained and experiments show that PRAM algorithms do often not achieve the expected speedup ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

SCG '93: Proceedings of the ninth annual symposium on Computational geometry

July 1993

406 pages

ISBN:0897915828

DOI:10.1145/160985

Chairman:
Chee Yap

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 July 1993

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

9SCG93

Sponsor:

9SCG93: Ninth Symposium on Computational Geometry

May 18 - 21, 1993

California, San Diego, USA

Acceptance Rates

Overall Acceptance Rate 625 of 1,685 submissions, 37%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

120
Total Citations
View Citations
499
Total Downloads

Downloads (Last 12 months)36
Downloads (Last 6 weeks)6

Reflects downloads up to 14 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Bogning Tepiele HKengne Tchendji VAkong Onabid MMyoupo JNkonjoh Ngomade A(2024)Dominant Point-Based Sequential and Parallel Algorithms for the Multiple Sequential Substring Constrained-LCS ProblemACM Transactions on Parallel Computing10.1145/369665711:4(1-31)Online publication date: 23-Sep-2024
https://dl.acm.org/doi/10.1145/3696657
Nanfack ALe Mahec GDequen G(2024)Optimizing Privacy While Limiting Information Loss in Distributed Data Anonymization2024 IEEE International Conference on Big Data (BigData)10.1109/BigData62323.2024.10825321(352-359)Online publication date: 15-Dec-2024
https://doi.org/10.1109/BigData62323.2024.10825321
Lacmou Zeutouo JKengne Tchendji VMyoupo J(2022)Four-splitting based coarse-grained multicomputer parallel algorithm for the optimal binary search tree problemInternational Journal of Parallel, Emergent and Distributed Systems10.1080/17445760.2022.210216837:6(659-679)Online publication date: 28-Jul-2022
https://doi.org/10.1080/17445760.2022.2102168
Kengne Tchendji VBogning Tepiele HAkong Onabid MMyoupo JLacmou Zeutouo J(2022)A coarse-grained multicomputer parallel algorithm for the sequential substring constrained longest common subsequence problemParallel Computing10.1016/j.parco.2022.102927111:COnline publication date: 1-Jul-2022
https://dl.acm.org/doi/10.1016/j.parco.2022.102927
Stefanes MRubert DSoares J(2019)Scalable parallel algorithms for maximum matching and Hamiltonian circuit in convex bipartite graphsTheoretical Computer Science10.1016/j.tcs.2019.10.042Online publication date: Nov-2019
https://doi.org/10.1016/j.tcs.2019.10.042
Agarwal PFox KMunagala KNath AMilo TTan W(2016)Parallel Algorithms for Constructing Range and Nearest-Neighbor Searching Data StructuresProceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems10.1145/2902251.2902303(429-440)Online publication date: 15-Jun-2016
https://dl.acm.org/doi/10.1145/2902251.2902303
Huang JZhang RBuyya RChen JWu Y(2016)Heads-Join: Efficient Earth Mover's Distance Similarity Joins on HadoopIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2015.246235427:6(1660-1673)Online publication date: 1-Jun-2016
https://doi.org/10.1109/TPDS.2015.2462354
Amaris MCordeiro DGoldman ACamargo R(2015)A Simple BSP-based Model to Predict Execution Time in GPU ApplicationsProceedings of the 2015 IEEE 22nd International Conference on High Performance Computing (HiPC)10.1109/HiPC.2015.34(285-294)Online publication date: 16-Dec-2015
https://dl.acm.org/doi/10.1109/HiPC.2015.34
Afrati FKoutris PSuciu DUllman J(2015)Parallel Skyline QueriesTheory of Computing Systems10.1007/s00224-015-9627-357:4(1008-1037)Online publication date: 1-Nov-2015
https://dl.acm.org/doi/10.1007/s00224-015-9627-3
Senger HGil‐Costa VArantes LMarcondes CMarín MSato Lda Silva F(2015)BSP cost and scalability analysis for MapReduce operationsConcurrency and Computation: Practice and Experience10.1002/cpe.362828:8(2503-2527)Online publication date: 7-Oct-2015
https://doi.org/10.1002/cpe.3628
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Solving large graph problems on coarse-grained multicomputers

Efficient External Memory Algorithms by Simulating Coarse-Grained Parallel Algorithms

Coarse grained parallel algorithms for graph matching