What Do a Longest Increasing Subsequence and a Longest Decreasing Subsequence Know about Each Other?

被引：0
|
作者：
Itskovich, Elizabeth J. [1 ]
Levit, Vadim E. [1 ]
机构：
[1] Ariel Univ, Dept Comp Sci, IL-40700 Ariel, Israel
来源：
ALGORITHMS | 2019年 / 12卷 / 11期
关键词：
Erdos-Szekeres theorem; longest increasing sequence; longest decreasing sequence;
D O I：
10.3390/a12110237
中图分类号：
TP18 [人工智能理论];
学科分类号：
081104 ; 0812 ; 0835 ; 1405 ;
摘要：
As a kind of converse of the celebrated Erdos-Szekeres theorem, we present a necessary and sufficient condition for a sequence of length n to contain a longest increasing subsequence and a longest decreasing subsequence of given lengths x and y, respectively.
引用
收藏
页数：3
相关论文
共 50 条
  • [41] On the longest common parameterized subsequence
    Keller, Orgad
    Kopelowitz, Tsvi
    Lewenstein, Moshe
    THEORETICAL COMPUTER SCIENCE, 2009, 410 (51) : 5347 - 5353
  • [42] On the longest common parameterized subsequence
    Keller, Orgad
    Kopelowitz, Tsvi
    Lewenstein, Moshe
    COMBINATORIAL PATTERN MATCHING, 2008, 5029 : 303 - +
  • [43] Exemplar longest common subsequence
    Bonizzoni, Paola
    Della Vedova, Gianluca
    Dondi, Riccardo
    Fertin, Guillaume
    Vialette, Stephane
    COMPUTATIONAL SCIENCE - ICCS 2006, PT 2, PROCEEDINGS, 2006, 3992 : 622 - 629
  • [44] Parallel Longest Increasing Subsequence and van Emde Boas Trees
    Gu, Yan
    Men, Ziyang
    Shen, Zheqi
    Sun, Yihan
    Wan, Zijin
    PROCEEDINGS OF THE 35TH ACM SYMPOSIUM ON PARALLELISM IN ALGORITHMS AND ARCHITECTURES, SPAA 2023, 2023, : 327 - 340
  • [45] A linear space algorithm for computing a longest common increasing subsequence
    Sakai, Yoshifumi
    INFORMATION PROCESSING LETTERS, 2006, 99 (05) : 203 - 207
  • [46] A concentration bound for the longest increasing subsequence of a randomly chosen involution
    Kiwi, Marcos
    DISCRETE APPLIED MATHEMATICS, 2006, 154 (13) : 1816 - 1823
  • [47] Tight Conditional Lower Bounds for Longest Common Increasing Subsequence
    Lech Duraj
    Marvin Künnemann
    Adam Polak
    Algorithmica, 2019, 81 : 3968 - 3992
  • [48] On Differentially Private Longest Increasing Subsequence Computation in Data Stream
    Bonomi, Luca
    Xiong, Li
    TRANSACTIONS ON DATA PRIVACY, 2016, 9 (01) : 73 - 100
  • [49] Non-universality for longest increasing subsequence of a random walk
    Pemantle, Robin
    Peres, Yuval
    ALEA-LATIN AMERICAN JOURNAL OF PROBABILITY AND MATHEMATICAL STATISTICS, 2017, 14 (01): : 327 - 336
  • [50] Tight Conditional Lower Bounds for Longest Common Increasing Subsequence
    Duraj, Lech
    Kuennemann, Marvin
    Polak, Adam
    ALGORITHMICA, 2019, 81 (10) : 3968 - 3992
12345