Improved bounds on the average length of longest common subsequences

DOI10.1145/1516512.1516519zbMath1325.68308WikidataQ56171968 ScholiaQ56171968MaRDI QIDQ3452214

George S. Lueker

Publication date: 11 November 2015

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1516512.1516519

zbMATH Keywords

dynamic programming; average-case analysis; longest common subsequences; Arratia-Steele conjecture

Mathematics Subject Classification ID

68W40: Analysis of algorithms

05A15: Exact enumeration problems, generating functions

68R15: Combinatorics on words

05A05: Permutations, words, matrices

60C05: Combinatorial probability

68W32: Algorithms on strings