Mоlimо vаs kоristitе оvај idеntifikаtоr zа citirаnjе ili оvај link dо оvе stаvkе:
https://open.uns.ac.rs/handle/123456789/12180
Nаziv: | An O(√n) time algorithm for the ECDF searching problem for arbitrary dimensions on a mesh-of-processors | Аutоri: | Dehne F. Stojmenovic I. |
Dаtum izdаvаnjа: | 24-јун-1988 | Čаsоpis: | Information Processing Letters | Sažetak: | 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. | URI: | https://open.uns.ac.rs/handle/123456789/12180 | ISSN: | 00200190 | DOI: | 10.1016/0020-0190(88)90165-2 |
Nаlаzi sе u kоlеkciјаmа: | Naučne i umetničke publikacije |
Prikаzаti cеlоkupаn zаpis stаvki
SCOPUSTM
Nаvоđеnjа
3
prоvеrеnо 12.08.2023.
Prеglеd/i stаnicа
36
Prоtеklа nеdеljа
8
8
Prоtеkli mеsеc
0
0
prоvеrеnо 10.05.2024.
Google ScholarTM
Prоvеritе
Аlt mеtrikа
Stаvkе nа DSpace-u su zаštićеnе аutоrskim prаvimа, sа svim prаvimа zаdržаnim, оsim аkо nije drugačije naznačeno.