A work-optimal CGM algorithm for the longest increasing subsequence problem

被引：0
|
作者：
Garcia, T [1 ]
Myoupo, JF [1 ]
Semé, D [1 ]
机构：
[1] Univ Picardie Jules Verne, Lab Rech Informat Amiens, LaRIA, F-80000 Amiens, France
来源：
PDPTA'2001: PROCEEDINGS OF THE INTERNATIONAL CONFERENCE ON PARALLEL AND DISTRIBUTED PROCESSING TECHNIQUES AND APPLICATIONS | 2001年
关键词：
parallel algorithms; coarse grained multicompaters; longest increasing subsequence;
D O I：
暂无
中图分类号：
TP3 [计算技术、计算机技术];
学科分类号：
0812 ;
摘要：
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(N-2/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-2).
引用
收藏
页码：563 / 569
页数：5
相关论文
共 50 条
  • [1] A CGM algorithm solving the longest increasing subsequence problem
    Seme, David
    COMPUTATIONAL SCIENCE AND ITS APPLICATIONS - ICCSA 2006, PT 5, 2006, 3984 : 10 - 21
  • [2] The Longest Wave Subsequence Problem: Generalizations of the Longest Increasing Subsequence Problem
    Chen, Guan-Zhi
    Yang, Chang-Biau
    Chang, Yu-Cheng
    INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE, 2025, 36 (02) : 203 - 218
  • [3] An algorithm for solving the longest increasing circular subsequence problem
    Deorowicz, Sebastian
    INFORMATION PROCESSING LETTERS, 2009, 109 (12) : 630 - 634
  • [4] An efficient parallel algorithm for the longest increasing subsequence problem on a LARPBS
    Seme, David
    Youlou, Sidney
    EIGHTH INTERNATIONAL CONFERENCE ON PARALLEL AND DISTRIBUTED COMPUTING, APPLICATIONS AND TECHNOLOGIES, PROCEEDINGS, 2007, : 251 - 258
  • [5] The longest common increasing subsequence problem
    Bai, YS
    Weems, BP
    Proceedings of the 8th Joint Conference on Information Sciences, Vols 1-3, 2005, : 362 - 366
  • [6] A diagonal-based algorithm for the longest common increasing subsequence problem
    Lo, Shou-Fu
    Tseng, Kuo-Tsung
    Yang, Chang-Biau
    Huang, Kuo-Si
    THEORETICAL COMPUTER SCIENCE, 2020, 815 : 69 - 78
  • [7] A Sub-Quadratic Algorithm for the Longest Common Increasing Subsequence Problem
    Duraj, Lech
    37TH INTERNATIONAL SYMPOSIUM ON THEORETICAL ASPECTS OF COMPUTER SCIENCE (STACS 2020), 2020, 154
  • [8] The Merged Longest Common Increasing Subsequence Problem
    Lee, Chien-Ting
    Yang, Chang-Biau
    Huang, Kuo-Si
    RECENT CHALLENGES IN INTELLIGENT INFORMATION AND DATABASE SYSTEMS, ACIIDS 2024, PT I, 2024, 2144 : 202 - 212
  • [9] On Two Variants of the Longest Increasing Subsequence Problem
    Deorowicz, Sebastian
    Grabowski, Szymon
    MAN-MACHINE INTERACTIONS, 2009, 59 : 541 - +
  • [10] AN ALGORITHM FOR THE DETERMINATION OF A LONGEST INCREASING SUBSEQUENCE IN A SEQUENCE
    ORLOWSKI, M
    PACHTER, M
    COMPUTERS & MATHEMATICS WITH APPLICATIONS, 1989, 17 (07) : 1073 - 1075
12345