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 条
  • [1] 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
  • [2] On the longest common increasing binary subsequence
    Houdre, Christian
    Lember, Juri
    Matzinger, Heinrich
    COMPTES RENDUS MATHEMATIQUE, 2006, 343 (09) : 589 - 594
  • [3] The longest almost-increasing subsequence
    Elmasry, Amr
    INFORMATION PROCESSING LETTERS, 2010, 110 (16) : 655 - 658
  • [4] The Longest Almost-Increasing Subsequence
    Elmasry, Amr
    COMPUTING AND COMBINATORICS, 2010, 6196 : 338 - 347
  • [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] On the longest increasing subsequence of a circular list
    Albert, M. H.
    Atkinson, M. D.
    Nussbaum, Doron
    Sack, Jorg-Rudiger
    Santoro, Nicola
    INFORMATION PROCESSING LETTERS, 2007, 101 (02) : 55 - 59
  • [7] On Two Variants of the Longest Increasing Subsequence Problem
    Deorowicz, Sebastian
    Grabowski, Szymon
    MAN-MACHINE INTERACTIONS, 2009, 59 : 541 - +
  • [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] Improved Dynamic Algorithms for Longest Increasing Subsequence
    Kociumaka, Tomasz
    Seddighin, Saeed
    STOC '21: PROCEEDINGS OF THE 53RD ANNUAL ACM SIGACT SYMPOSIUM ON THEORY OF COMPUTING, 2021, : 640 - 653
  • [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