Enumerating longest increasing subsequences and patience sorting

Abstract: 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"
}