{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,2]],"date-time":"2022-04-02T05:50:18Z","timestamp":1648878618848},"reference-count":0,"publisher":"World Scientific Pub Co Pte Lt","issue":"02","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Parallel Process. Lett."],"published-print":{"date-parts":[[1995,6]]},"abstract":"<jats:p> The fundamental problem of minimum computation has several well-studied generalizations such as prefix minima, range minima, and all nearest smaller values computations. Recent papers introduced parallel algorithms for these problems when the n input elements are given from an integer domain [1..s], obtaining O( lglglg s) running time and linear work for s \u2265 n. However, most of these algorithms have the running time of O( lglglg n) (rather than O( lglglg s)) for all values of s \u2264 n, except for the case of s = O(1) in which case the running time is O(\u03b1(n)). In this paper we focus on the range s \u2264 n and provide linear-work algorithms whose running time O( lglglg s + f(n)) is for all s \u2265 0, where f(n) is either one of the slow growing functions lg *n or \u03b1(n). We show how to generalize our algorithms to the case that the domain size s is unknown, with the same complexities. (All previous algorithms work only under the assumption that the domain size s is known.) Moreover, we make our algorithms output-sensitive with the lglglgs term replaced by lglglg M, where M is the maximum input value. In fact, for the minimum computation problem the running time is O( lglglg m) for all s \u2265 0, where m is the minimum input value. <\/jats:p>","DOI":"10.1142\/s0129626495000205","type":"journal-article","created":{"date-parts":[[2004,11,10]],"date-time":"2004-11-10T11:14:37Z","timestamp":1100085277000},"page":"223-230","source":"Crossref","is-referenced-by-count":2,"title":["FAST PARALLEL ALGORITHMS FOR MINIMUM AND RELATED PROBLEMS WITH SMALL INTEGER INPUTS"],"prefix":"10.1142","volume":"05","author":[{"given":"OMER","family":"BERKMAN","sequence":"first","affiliation":[{"name":"Department of Computer Science, King's College London, England"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"YOSSI","family":"MATIAS","sequence":"additional","affiliation":[{"name":"AT&amp;T Bell Laboratories 600 Mountain Avenue, Murray Hill, NJ 07974-0636, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2011,11,21]]},"container-title":["Parallel Processing Letters"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129626495000205","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,6]],"date-time":"2019-08-06T16:17:31Z","timestamp":1565108251000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129626495000205"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995,6]]},"references-count":0,"journal-issue":{"issue":"02","published-online":{"date-parts":[[2011,11,21]]},"published-print":{"date-parts":[[1995,6]]}},"alternative-id":["10.1142\/S0129626495000205"],"URL":"https:\/\/doi.org\/10.1142\/s0129626495000205","relation":{},"ISSN":["0129-6264","1793-642X"],"issn-type":[{"value":"0129-6264","type":"print"},{"value":"1793-642X","type":"electronic"}],"subject":[],"published":{"date-parts":[[1995,6]]}}}