{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,4]],"date-time":"2022-04-04T09:41:52Z","timestamp":1649065312407},"reference-count":0,"publisher":"World Scientific Pub Co Pte Lt","issue":"01n02","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Parallel Process. Lett."],"published-print":{"date-parts":[[1994,6]]},"abstract":"<jats:p> We present a parallel algorithm for the Concave Least Weight Subsequence (CLWS) problem that exhibits the following work-time trade-off: Given a parameter p, the algorithm runs in [Formula: see text] time using p processors. By a known reduction of the Huffman Tree problem to the CLWS problem, we obtain the same complexity bounds for the Huffman Tree problem. However, as we show, for the later problem there exists a simpler (and, in fact, slightly better) algorithm that exhibits a similar trade-off: Namely, for a given parameter p, p\u22651, the algorithm runs in [Formula: see text] time using p processors. <\/jats:p>","DOI":"10.1142\/s0129626494000053","type":"journal-article","created":{"date-parts":[[2004,11,19]],"date-time":"2004-11-19T02:21:13Z","timestamp":1100830873000},"page":"37-43","source":"Crossref","is-referenced-by-count":1,"title":["A WORK-TIME TRADE-OFF IN PARALLEL COMPUTATION OF HUFFMAN TREES AND CONCAVE LEAST WEIGHT SUBSEQUENCE PROBLEM"],"prefix":"10.1142","volume":"04","author":[{"given":"CHRISTOS","family":"LEVCOPOULOS","sequence":"first","affiliation":[{"name":"Department of Computer Science, Lund University S-211 00 Lund, Sweden"}]},{"given":"TERESA M.","family":"PRZYTYCKA","sequence":"additional","affiliation":[{"name":"Department of of Math. and Computer Science, Odense University DK-5230 Odense M, Denmark"}]}],"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\/S0129626494000053","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T13:31:46Z","timestamp":1565184706000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129626494000053"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1994,6]]},"references-count":0,"journal-issue":{"issue":"01n02","published-online":{"date-parts":[[2011,11,21]]},"published-print":{"date-parts":[[1994,6]]}},"alternative-id":["10.1142\/S0129626494000053"],"URL":"https:\/\/doi.org\/10.1142\/s0129626494000053","relation":{},"ISSN":["0129-6264","1793-642X"],"issn-type":[{"value":"0129-6264","type":"print"},{"value":"1793-642X","type":"electronic"}],"subject":[],"published":{"date-parts":[[1994,6]]}}}