File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Article: Finding least-weight subsequences with fewer processors

TitleFinding least-weight subsequences with fewer processors
Authors
KeywordsDynamic Programming
Monotone Matrix
Parallel Algorithms
Issue Date1993
PublisherSpringer New York LLC. The Journal's web site is located at http://link.springer.de/link/service/journals/00453/index.htm
Citation
Algorithmica, 1993, v. 9 n. 6, p. 615-628 How to Cite?
AbstractBy restricting weight functions to satisfy the quadrangle inequality or the inverse quadrangle inequality, significant progress has been made in developing efficient sequential algorithms for the least-weight subsequence problem [10], [9], [12], [16]. However, not much is known on the improvement of the naive parallel algorithm for the problem, which is fast but demands too many processors (i.e., it takes O(log 2n) time on a CREW PRAM with n 3/log n processors). In this paper we show that if the weight function satisfies the inverse quadrangle inequality, the problem can be solved on a CREW PRAM in O(log 2n log log n) time with n/log log n processors, or in O(log 2n) time with n log n processors. Notice that the processor-time complexity of our algorithm is much closer to the almost linear-time complexity of the best-known sequential algorithm [12]. © 1993 Springer-Verlag New York Inc.
Persistent Identifierhttp://hdl.handle.net/10722/152238
ISSN
2023 Impact Factor: 0.9
2023 SCImago Journal Rankings: 0.905
ISI Accession Number ID

 

DC FieldValueLanguage
dc.contributor.authorLam, TWen_US
dc.contributor.authorChan, Kfen_US
dc.date.accessioned2012-06-26T06:36:41Z-
dc.date.available2012-06-26T06:36:41Z-
dc.date.issued1993en_US
dc.identifier.citationAlgorithmica, 1993, v. 9 n. 6, p. 615-628en_US
dc.identifier.issn0178-4617en_US
dc.identifier.urihttp://hdl.handle.net/10722/152238-
dc.description.abstractBy restricting weight functions to satisfy the quadrangle inequality or the inverse quadrangle inequality, significant progress has been made in developing efficient sequential algorithms for the least-weight subsequence problem [10], [9], [12], [16]. However, not much is known on the improvement of the naive parallel algorithm for the problem, which is fast but demands too many processors (i.e., it takes O(log 2n) time on a CREW PRAM with n 3/log n processors). In this paper we show that if the weight function satisfies the inverse quadrangle inequality, the problem can be solved on a CREW PRAM in O(log 2n log log n) time with n/log log n processors, or in O(log 2n) time with n log n processors. Notice that the processor-time complexity of our algorithm is much closer to the almost linear-time complexity of the best-known sequential algorithm [12]. © 1993 Springer-Verlag New York Inc.en_US
dc.languageengen_US
dc.publisherSpringer New York LLC. The Journal's web site is located at http://link.springer.de/link/service/journals/00453/index.htmen_US
dc.relation.ispartofAlgorithmicaen_US
dc.subjectDynamic Programmingen_US
dc.subjectMonotone Matrixen_US
dc.subjectParallel Algorithmsen_US
dc.titleFinding least-weight subsequences with fewer processorsen_US
dc.typeArticleen_US
dc.identifier.emailLam, TW:twlam@cs.hku.hken_US
dc.identifier.authorityLam, TW=rp00135en_US
dc.description.naturelink_to_subscribed_fulltexten_US
dc.identifier.doi10.1007/BF01190159en_US
dc.identifier.scopuseid_2-s2.0-0027610382en_US
dc.identifier.volume9en_US
dc.identifier.issue6en_US
dc.identifier.spage615en_US
dc.identifier.epage628en_US
dc.identifier.isiWOS:A1993LD15100008-
dc.publisher.placeUnited Statesen_US
dc.identifier.scopusauthoridLam, TW=7202523165en_US
dc.identifier.scopusauthoridChan, Kf=24331046500en_US
dc.identifier.issnl0178-4617-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats