Eighth International Conference on Parallel and Distributed Computing, Applications and Technologies (PDCAT 2007) An Efficient Parallel Algorithm for the Longest Increasing Subsequence Problem on a LARPBS Adelaide, Australia December 03-December 06 ISBN: 0-7695-3049-4
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/PDCAT.2007.74
In this paper, we give a parallel algorithm for the longest increasing subsequence problem on a LARPBS, one of the recently proposed parallel model based on optical bus. For a sequence of n integers, we solve the longest increasing subsequence problem in O(k) time using n processors where k is the length of the solution. Then, we give an algorithm for the maximal layers problem that runs in O(k+log(n)) time for a set of n points where k is the number of layers on a n-processor array. To our knowledge, this is the fastest algorithm for that problem.
Citation:
David Seme, Sideny Youlou, "An Efficient Parallel Algorithm for the Longest Increasing Subsequence Problem on a LARPBS," pdcat, pp.251-258, Eighth International Conference on Parallel and Distributed Computing, Applications and Technologies (PDCAT 2007), 2007 Usage of this product signifies your acceptance of the Terms of Use. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb