Skip to main content
Springer Nature Link
Log in

LIS using backtracking and branch-and-bound approaches

  • Special Issue REDSET 2016 of CSIT
  • Published:
CSI Transactions on ICT Aims and scope Submit manuscript

Abstract

Finding the longest increasing subsequence and its length from a sequence of finite integers is an NP-hard problem. Many significant efforts have been put to provide solutions to this problem with time complexity O(n log n) (n is the size of sequence), O(n2), O(n log log k), O(n) (using parallel processing) and more. In this paper we provide conceptual views of LIS and its solution using two approaches—backtracking and branch-and-bound. Its implementation using backtracking approach takes time O(2n) and the other solution based on the concept of branch-and-bound approach takes O(n2) time. Both solutions are efficient than the bruit force approach.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Canada)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2

Similar content being viewed by others

References

  1. Tsai YT (2003) The constrained longest common subsequence problem. Inf Process Lett 88(4):173–176

    Article  MathSciNet  MATH  Google Scholar 

  2. Delcher AL et al (1999) Alignment of whole genomes. Nucl Acids Res 27(11):2369–2376

    Article  Google Scholar 

  3. Lascoux, A, Bernard L, Jean-Yves T (2002) The plactic monoid. In: Algebraic Combinatoric on Words, pp 10

  4. Cormen TH (2009) Introduction to algorithms. MIT Press, Cambridge

    MATH  Google Scholar 

  5. Schensted C (1961) Longest increasing and decreasing subsequences. Can J Math 13(2):179–191

    Article  MathSciNet  MATH  Google Scholar 

  6. Fredman ML (1975) On computing the length of longest increasing subsequences. Discrete Math 11(1):29–35

    Article  MathSciNet  MATH  Google Scholar 

  7. Alam MR, Rahman MS (2013) A divide and conquer approach and a work-optimal parallel algorithm for the LIS problem. Inf Process Lett 113(13):470–476

    Article  MathSciNet  MATH  Google Scholar 

  8. Bespamyatnikh S, Segal M (2000) Enumerating longest increasing subsequences and patience sorting. Inf Process Lett 761:7–11

    Article  MathSciNet  MATH  Google Scholar 

  9. van Emde B (1977) Peter: preserving order in a forest in less than logarithmic time and linear space. Inf Process Lett 6(3):80–82

    Article  MATH  Google Scholar 

  10. Crochemore M, Porat E (2010) Fast computation of a longest increasing subsequence and application. Inf Comput 208(9):1054–1059

    Article  MathSciNet  MATH  Google Scholar 

  11. Saks M, Seshadhri C (2010) Estimating the longest increasing sequence in polylogarithmic time. In: Foundations of computer science (FOCS), 51st Annual IEEE symposium on IEEE, pp 458–467

  12. Elmasry A (2010) The longest almost-increasing subsequence. In: Computing and combinatorics. Springer, Berlin, pp 338–347

  13. Albert MH et al (2004) Longest increasing subsequences in sliding windows. Theor Comput Sci 321(2):405–414

    Article  MathSciNet  MATH  Google Scholar 

  14. Chen E, Yang L, Yuan H (2007) Longest increasing subsequences in windows based on canonical antichain partition. Theor Comput Sci 378(3):223–236

    Article  MathSciNet  MATH  Google Scholar 

  15. Albert MH et al (2007) On the longest increasing subsequence of a circular list. Inf Process Lett 101(2):55–59

    Article  MathSciNet  MATH  Google Scholar 

  16. Deorowicz S (2009) An algorithm for solving the longest increasing circular subsequence problem. Inf Process Lett 109(12):630–634

    Article  MathSciNet  MATH  Google Scholar 

  17. Tseng CT, Yang CB, Ann HY (2009) Minimum height and sequence constrained longest increasing subsequence. J Internet Technol 10(2):173–178

    Google Scholar 

  18. Horowitz, Sahni, Rajasekaran (1998) Fundamentals of computer algorithms. Galgotia Publica tions Pvt. Ltd.

Download references

Author information

Authors and Affiliations

  1. Department of Computer Science, FET, Manav Rachna International University, Faridabad, India

    Seema Rani

  2. Department of Computer Science, Jaypee Institute of Information Technology University, Noida, India

    Dharmveer Singh Rajpoot

Authors
  1. Seema Rani
    View author publications

    You can also search for this author inPubMed Google Scholar

  2. Dharmveer Singh Rajpoot
    View author publications

    You can also search for this author inPubMed Google Scholar

Corresponding author

Correspondence to Seema Rani.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Rani, S., Rajpoot, D.S. LIS using backtracking and branch-and-bound approaches. CSIT 4, 87–93 (2016). https://doi.org/10.1007/s40012-016-0108-x

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s40012-016-0108-x

Keywords