Loading...
Please wait, while we are loading the content...
Similar Documents
Longest Common Patterns and Longest Increasing Subsequences
| Content Provider | Semantic Scholar |
|---|---|
| Author | Godbole, Anant |
| Copyright Year | 2017 |
| Abstract | In this talk, we explore extensions of two classical problems to pairs of permutations. First, analogously with the problem of the longest common subsequence of two random strings, we study the longest common order isomorphic pattern between two random permutations on [n]. Second, analogously with the problem of the longest monotone subsequence of a random permutation, we study the longest increasing subsequence of the random multiset [n] ∪ [n]. Extending the number “two” to “k” yields interesting combinatorial identities. This is joint work with Jon Dewitt, Mike Earnest, and Yevgeniy Rudoy. |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | http://www.science.fau.edu/combinatorics/godboleanant.pdf |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
