Please use this identifier to cite or link to this item:
https://open.uns.ac.rs/handle/123456789/12180
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Dehne F. | en |
dc.contributor.author | Stojmenovic I. | en |
dc.date.accessioned | 2020-03-03T14:47:30Z | - |
dc.date.available | 2020-03-03T14:47:30Z | - |
dc.date.issued | 1988-06-24 | en |
dc.identifier.issn | 00200190 | en |
dc.identifier.uri | https://open.uns.ac.rs/handle/123456789/12180 | - |
dc.description.abstract | Dehne (1986) presented an optimal O(√n) time parallel algorithm for solving the ECDF searching problem for a set of n points in two- and three-dimensional space on a mesh-of-processors of size n. However, it remained an open problem whether such an optimal solution exists for the d-dimensional ECDF searching problem for d≥4. In this paper we solve this problem by presenting an optimal O(√n) time parallel solution to the d-dimensional ECDF searching problem for arbitrary dimension d = O(1) on a mesh-of-processors of size n. The algorithm has several interesting implications. Among others, the following problems can now be solved on a mesh-of-processors in (asymptotically optimal) time O(√n) for arbitrary dimension d = O(1): the d-dimensional maximal element determination problem, the d-dimensional hypercube containment counting problem, and the d-dimensional hypercube intersection counting problem. The latter two problems can be mapped to the 2d-dimensional ECDF searching problem but require an efficient solution to this problem for at least d≥4. © 1988. | en |
dc.relation.ispartof | Information Processing Letters | en |
dc.title | An O(√n) time algorithm for the ECDF searching problem for arbitrary dimensions on a mesh-of-processors | en |
dc.type | Journal/Magazine Article | en |
dc.identifier.doi | 10.1016/0020-0190(88)90165-2 | en |
dc.identifier.scopus | 2-s2.0-0024031590 | en |
dc.identifier.url | https://api.elsevier.com/content/abstract/scopus_id/0024031590 | en |
dc.relation.lastpage | 70 | en |
dc.relation.firstpage | 67 | en |
dc.relation.issue | 2 | en |
dc.relation.volume | 28 | en |
item.grantfulltext | none | - |
item.fulltext | No Fulltext | - |
Appears in Collections: | Naučne i umetničke publikacije |
SCOPUSTM
Citations
3
checked on Aug 12, 2023
Page view(s)
36
Last Week
8
8
Last month
0
0
checked on May 10, 2024
Google ScholarTM
Check
Altmetric
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.