Article

A work-optimal CGM algorithm for the LIS problem

Authors:

Garcia Thierry,

Myoupo Jean-Frédéric,

Semé DavidAuthors Info & Claims

SPAA '01: Proceedings of the thirteenth annual ACM symposium on Parallel algorithms and architectures

Pages 330 - 331

https://doi.org/10.1145/378580.378756

Published: 02 June 2019 Publication History

Get Access

Abstract

This paper presents a work-optimal CGM algorithm that solves the Longest Increasing Subsequence Problem. It can be implemented in the CGM with P processors in O(N2 ÷P) time and O(P) communication steps. It is the first CGM algorithm for this problem and it is work-optimal since the sequential algorithm has a complexity of O(N²).

Cited By

View all

Cao NHuang SSu HAgrawal KShun J(2023)Nearly Optimal Parallel Algorithms for Longest Increasing SubsequenceProceedings of the 35th ACM Symposium on Parallelism in Algorithms and Architectures10.1145/3558481.3591078(249-259)Online publication date: 17-Jun-2023
https://dl.acm.org/doi/10.1145/3558481.3591078
Gu YMen ZShen ZSun YWan ZAgrawal KShun J(2023)Parallel Longest Increasing Subsequence and van Emde Boas TreesProceedings of the 35th ACM Symposium on Parallelism in Algorithms and Architectures10.1145/3558481.3591069(327-340)Online publication date: 17-Jun-2023
https://dl.acm.org/doi/10.1145/3558481.3591069
Shen ZWan ZGu YSun YAgrawal KLee I(2022)Many Sequential Iterative Algorithms Can Be Parallel and (Nearly) Work-efficientProceedings of the 34th ACM Symposium on Parallelism in Algorithms and Architectures10.1145/3490148.3538574(273-286)Online publication date: 11-Jul-2022
https://dl.acm.org/doi/10.1145/3490148.3538574
Show More Cited By

Index Terms

Recommendations

A work-optimal deterministic algorithm for the asynchronous certified write-all problem
PODC '03: Proceedings of the twenty-second annual symposium on Principles of distributed computing

In their SIAM J. on Computing paper [27] from 1992, Martel et al. posed a question for developing a work-optimal deterministic asynchronous algorithm for the fundamental load-balancing and synchronization problem called Certified Write-All. In this ...
Work-Time Optimal k-Merge Algorithms on the PRAM

For 2 k n, the k-merge problem is to merge a collection of k sorted sequences of total length n into a new sorted sequence. The k-merge problem is fundamental as it provides a common generalization of both merging and sorting. The main contribution of ...
An optimal distributed (Δ+1)-coloring algorithm?
STOC 2018: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing

Vertex coloring is one of the classic symmetry breaking problems studied in distributed computing. In this paper we present a new algorithm for (Δ+1)-list coloring in the randomized LOCAL model running in O(log^∗n + Det_d(poly logn)) time, where Det_d(n′) ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

SPAA '01: Proceedings of the thirteenth annual ACM symposium on Parallel algorithms and architectures

July 2001

340 pages

ISBN:1581134096

DOI:10.1145/378580

Chairman:
Arnold Rosenberg
Univ. of Massachusetts

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 02 June 2019

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

SPAA01

Sponsor:

SPAA01: 13th ACM Symposium on Parallel Algorithms and Architectures

Crete Island, Greece

Acceptance Rates

SPAA '01 Paper Acceptance Rate 34 of 93 submissions, 37%;

Overall Acceptance Rate 447 of 1,461 submissions, 31%

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 11 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Cao NHuang SSu HAgrawal KShun J(2023)Nearly Optimal Parallel Algorithms for Longest Increasing SubsequenceProceedings of the 35th ACM Symposium on Parallelism in Algorithms and Architectures10.1145/3558481.3591078(249-259)Online publication date: 17-Jun-2023
https://dl.acm.org/doi/10.1145/3558481.3591078
Gu YMen ZShen ZSun YWan ZAgrawal KShun J(2023)Parallel Longest Increasing Subsequence and van Emde Boas TreesProceedings of the 35th ACM Symposium on Parallelism in Algorithms and Architectures10.1145/3558481.3591069(327-340)Online publication date: 17-Jun-2023
https://dl.acm.org/doi/10.1145/3558481.3591069
Shen ZWan ZGu YSun YAgrawal KLee I(2022)Many Sequential Iterative Algorithms Can Be Parallel and (Nearly) Work-efficientProceedings of the 34th ACM Symposium on Parallelism in Algorithms and Architectures10.1145/3490148.3538574(273-286)Online publication date: 11-Jul-2022
https://dl.acm.org/doi/10.1145/3490148.3538574
Semé D(2006)A CGM algorithm solving the longest increasing subsequence problemProceedings of the 2006 international conference on Computational Science and Its Applications - Volume Part V10.1007/11751649_2(10-21)Online publication date: 8-May-2006
https://dl.acm.org/doi/10.1007/11751649_2

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

A work-optimal deterministic algorithm for the asynchronous certified write-all problem

Work-Time Optimal k-Merge Algorithms on the PRAM

An optimal distributed (Δ+1)-coloring algorithm?