Expected length of the longest common subsequence for large alphabets

DOI10.1016/j.aim.2004.10.012zbMath1087.68081WikidataQ56171970 ScholiaQ56171970MaRDI QIDQ2573406

Martin Loebl, Ji{ří} Matoušek, Marcos A. Kiwi

Publication date: 22 November 2005

Published in: Advances in Mathematics (Search for Journal in Brave)

Full work available at URL: http://hdl.handle.net/10533/176259

zbMATH Keywords

Expectation; Longest common subsequence; Longest increasing subsequence; Sankoff-Mainville conjecture

Mathematics Subject Classification ID

68R15: Combinatorics on words

60C05: Combinatorial probability

92B05: General biology and biomathematics

Related Items

The rate of the convergence of the mean score in random sequence comparison, Thermodynamical approach to the longest common subsequence problem, Standard deviation of the longest common subsequence, On suboptimal LCS-alignments for independent Bernoulli sequences with asymmetric distributions, A concentration bound for the longest increasing subsequence of a randomly chosen involution, On a Speculated Relation Between Chvátal–Sankoff Constants of Several Sequences

Cites Work

• An Efron-Stein inequality for nonsymmetric statistics
• On the length of the longest monotone subsequence in a random permutation
• Subadditive ergodic theory
• A variational problem for random Young tableaux
• Bounding the expected length of longest common subsequences and forests
• Increasing sequences of independent points on the planar lattice
• Longest Increasing and Decreasing Subsequences
• Longest common subsequences of two random sequences
• On the distribution of the length of the longest increasing subsequence of random permutations
• Longest increasing subsequences: from patience sorting to the Baik-Deift-Johansson theorem
• Recent progress in algebraic combinatorics
• Largest planar matching in random bipartite graphs
• Limit theorems for height fluctuations in a class of discrete space and time growth models
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item