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 条
  • [21] Estimating the Longest Increasing Subsequence in Nearly Optimal Time
    Andoni, Alexandr
    Nosatzki, Negev Shekel
    Sinha, Sandip
    Stein, Clifford
    2022 IEEE 63RD ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE (FOCS), 2022, : 708 - 719
  • [22] Efficient algorithms for finding a longest common increasing subsequence
    Wun-Tat Chan
    Yong Zhang
    Stanley P. Y. Fung
    Deshi Ye
    Hong Zhu
    Journal of Combinatorial Optimization, 2007, 13 : 277 - 288
  • [23] Longest Increasing Subsequence under Persistent Comparison Errors
    Barbara Geissmann
    Theory of Computing Systems, 2020, 64 : 662 - 680
  • [24] An algorithm for solving the longest increasing circular subsequence problem
    Deorowicz, Sebastian
    INFORMATION PROCESSING LETTERS, 2009, 109 (12) : 630 - 634
  • [25] The Length of the Longest Increasing Subsequence of a Random Mallows Permutation
    Carl Mueller
    Shannon Starr
    Journal of Theoretical Probability, 2013, 26 : 514 - 540
  • [26] Cyclic longest common subsequence
    Naiman, Aaron E.
    Farber, Eliav
    Stein, Yossi
    DISCRETE MATHEMATICS ALGORITHMS AND APPLICATIONS, 2023, 15 (04)
  • [27] Palindromic Subsequence Automata and Longest Common Palindromic Subsequence
    Hasan M.M.
    Islam A.S.M.S.
    Rahman M.S.
    Sen A.
    Mathematics in Computer Science, 2017, 11 (2) : 219 - 232
  • [28] On the Distribution of the Length of the Longest Increasing Subsequence in a Random Permutation
    James C. Fu
    Yu-Fei Hsieh
    Methodology and Computing in Applied Probability, 2015, 17 : 489 - 496
  • [29] A CGM algorithm solving the longest increasing subsequence problem
    Seme, David
    COMPUTATIONAL SCIENCE AND ITS APPLICATIONS - ICCSA 2006, PT 5, 2006, 3984 : 10 - 21
  • [30] On the Distribution of the Length of the Longest Increasing Subsequence in a Random Permutation
    Fu, James C.
    Hsieh, Yu-Fei
    METHODOLOGY AND COMPUTING IN APPLIED PROBABILITY, 2015, 17 (02) : 489 - 496
12345