Generalizations and Variants of the Largest Non-crossing Matching Problem in Random Bipartite Graphs

Details Generalizations and Variants of the Largest Non-crossing Matching Problem in Random Bipartite Graphs Generalizations and Variants of the Largest Non-crossing Matching Problem in Random Bipartite Graphs

2011-05-03

arxiv.org/abs/1105.0474v1

Mathematics

Combinatorics

32 pages, 5 figures

Scientific paper

We are interested in the statistics of the length of the longest increasing subsequence of 2-rowed lexicographically sorted arrays chosen according to distinct families of distributions D = (D_n)_n, and when n goes to infinity. This framework encompasses well studied problems such as the so called Longest Increasing Subsequence problem, the Longest Common Subsequence problem, problems concerning directed bond percolation models, among others. We define several natural families of distinct distributions and characterize the asymptotic behavior of the expected length of a longest increasing subsequence chosen according to them. In particular, we consider generalizations to d-rowed arrays as well as symmetry restricted two-rowed arrays.

Affiliated with

Also associated with

No associations

Rating

Generalizations and Variants of the Largest Non-crossing Matching Problem in Random Bipartite Graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Generalizations and Variants of the Largest Non-crossing Matching Problem in Random Bipartite Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Generalizations and Variants of the Largest Non-crossing Matching Problem in Random Bipartite Graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-692325