Finding maximal pairs with bounded gap

DOI10.1007/3-540-48452-3_11MaRDI QIDQ3024804zbMATH OpenFDO

Authors Gerth Stølting Brodal, Rune B. Lyngsø, Christian Nørgaard Storm Pedersen, Jens Stoye

Publication date 4 July 2005

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-48452-3_11

Mathematics Subject Classification ID

Searching and sorting (68P10) Analysis of algorithms and problem complexity (68Q25) Combinatorics on words (68R15) Nonnumerical algorithms (68W05)

Recommendations

• Tight bounds on maximal and maximum matchings
• Tight bounds on maximal and maximum matchings
• Bounds on maximum \(b\)-matchings
• Max-Min Problems of Searching for Two Disjoint Subsets
• Maximum gap labelings of graphs
• On maximum bipartite matching with separation
• scientific article; zbMATH DE number 866672
• Maximum induced matchings close to maximum matchings
• Finding maximum square-free 2-matchings in bipartite graphs
• Finding a Maximum Clique in an Arbitrary Graph

Cited in

(20)

• Discovering subword associations in strings in time linear in the output size
• On maximal repeats in strings
• Improved upper bounds on all maximal -gapped repeats and palindromes
• Tighter bounds and optimal algorithms for all maximal -gapped repeats and palindromes. Finding all maximal -gapped repeats and palindromes in optimal worst case time on integer alphabets
• Linear time algorithms for finding and representing all the tandem repeats in a string
• Algorithms for extracting motifs from biological weighted sequences
• Double string tandem repeats
• Reporting consecutive substring occurrences under bounded gap constraints
• Longest -gapped repeat and palindrome
• Reporting consecutive substring occurrences under bounded gap constraints
• A faster algorithm for computing maximal -gapped repeats in a string
• Identifying occurrences of maximal pairs in multiple strings
• Small-space LCE data structure with constant-time queries
• Optimal discovery of subword associations in strings
• scientific article; zbMATH DE number 7651094 (Why is no real title available?)
• Maximal closed substrings
• Finding maximal closed substrings
• Counting maximal-exponent factors in words
• Efficient algorithms to compute closed substrings
• Computing maximal-exponent factors in an overlap-free word

This page was built for publication: Finding maximal pairs with bounded gap

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3024804)