Two parallel algorithms for finding all minimal maximum subsequences

作     者：Dai, H. K. Wang, Z. 

作者机构：Oklahoma State Univ Dept Comp Sci Stillwater OK 74078 USA 

出 版 物：《JOURNAL OF COMPUTER AND SYSTEM SCIENCES》 (计算机与系统科学杂志)

年 卷 期：2019年第104卷

页      面：216-243页

核心收录：

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：We are grateful to the anonymous referees for their constructive and helpful comments and suggestions 

主　　题：All maximum subsequences Parallel algorithm Parallel random-access machine model Theory of random walk Message Passing Interface 

摘      要：A minimal maximum subsequence is a minimal subsequence with maximum cumulative sum. We present two parallel algorithms that find all successive minimal maximum subsequences: one on the parallel random-access model in logarithmic time with linear work, and the other with overlapping domain decomposition on cluster systems. We confirm the efficacy and efficiency of the latter algorithm for random sequences via: (1) an application of random-walk theory that derives an approximate probabilistic length upper bound for overlapping subsequences - thus facilitating concurrent/independent computations of all minimal maximum subsequences in hosting processors, and (2) an empirical study with normally-distributed random sequences. (C) 2018 Elsevier Inc. All rights reserved.