Name
Abstract | ||
|---|---|---|
For a distribution g over labeled bipartite (multi) graphs G = (W, M, E), |W| = |M| = n, let L(n) denote the size of the largest planar matching of G (here W and M are posets drawn on the plane as two ordered rows of nodes and edges are drawn as straight lines). We study the asymptotic (in n) behavior of L(n) for different distributions g. Two interesting instances of this problem are Ulam's longest increasing subsequence problem and the longest common subsequence problem. We focus on the case where g is the uniform distribution over the k-regular bipartite graphs on W and M. For k = o(n1/4), we establish that L(n)/√kn tends to 2 in probability when n → ∞. Convergence in mean is also studied. Furthermore, we show that if each of the n2 possible edges between W and M are chosen independently with probability 0 p L(n)/n tends to a constant γp in probability and in mean when n → ∞. |
Year | DOI | Venue |
|---|---|---|
2002 | 10.1002/rsa.10048 | Random Struct. Algorithms |
Keywords | Field | DocType |
random bipartite graph,interesting instance,different distributions g,uniform distribution,graphs g,largest planar,largest planar matching,longest common subsequence problem,subsequence problem,k-regular bipartite graph,distribution g,p l,longest common subsequence,longest increasing subsequence,bipartite graph | Row,Convergence (routing),Graph,Discrete mathematics,Combinatorics,Longest common subsequence problem,Longest increasing subsequence,Bipartite graph,Uniform distribution (continuous),Planar,Mathematics | Journal |
Volume | Issue | ISSN |
21 | 2 | 1042-9832 |
Citations | PageRank | References |
1 | 0.47 | 7 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Marcos A. Kiwi | 1 | 169 | 24.15 |
| Martin Loebl | 2 | 152 | 28.66 |