Enumerating longest increasing subsequences and patience sortingAbstract: In this paper we present three algorithms that solve three combinatorial optimization problems related to each other. One is the patience sorting game, invented as a practical method of sorting real decks of cards. The second algorithm computes the longest monotone increasing subsequence of the given sequence of n positive integers in the range 1,...,n. The third algorithm enumerates all the longest monotone increasing subsequences of the given permutation. @paper{bs-elis-00 , author = "S. Bespamyatnikh and M. Segal" , title = "Enumerating longest increasing subsequences and patience sorting" , journal = "Inform. Process. Lett." , year = 2000 , volume = 76 , number = "1-2" , pages = "7--11" } |