scientific article; zbMATH DE number 7561345

DOI10.4230/LIPIcs.FSTTCS.2018.40MaRDI QIDQ5090981

Karl Bringmann, Bhaskar Chaudhury

Publication date: 21 July 2022

Full work available at URL: https://arxiv.org/abs/1810.01238

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

algorithmsrun-length encodingcommunication complexitySETH

Mathematics Subject Classification ID

Mathematical aspects of software engineering (specification, verification, metrics, requirements, etc.) (68N30) Theory of computing (68Qxx)

Related Items (5)

Absent Subsequences in Words ⋮ Longest Common Subsequence with Gap Constraints ⋮ Subsequences in bounded ranges: matching and analysis problems ⋮ Absent subsequences in words ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Polynomial-time approximation algorithms for weighted LCS problem
• Computing a longest common subsequence that is almost increasing on sequences having no repeated elements
• Faster algorithms for computing longest common increasing subsequences
• Fast algorithms for computing tree LCS
• A new efficient algorithm for computing the longest common subsequence
• A fast algorithm for computing a longest common increasing subsequence
• The longest common subsequence problem for arc-annotated sequences
• An O(NP) sequence comparison algorithm
• A fast and simple algorithm for computing the longest common subsequence of run-length encoded strings
• Efficient algorithms for finding a longest common increasing subsequence
• Sparse LCS common substring alignment
• On the longest common parameterized subsequence
• Improving the worst-case performance of the Hunt-Szymanski strategy for the longest common subsequence of two strings
• The longest common subsequence problem revisited
• An \(O(ND)\) difference algorithm and its variations
• A longest common subsequence algorithm suitable for similar text strings
• On randomized one-round communication complexity
• Which problems have strongly exponential complexity?
• Longest common subsequence between run-length-encoded strings: a new algorithm with improved parallelism
• Finding a longest common subsequence between a run-length-encoded string and an uncompressed string
• Finding longest increasing and common subsequences in streaming data
• A new algorithm for optimal 2-constraint satisfaction and its implications
• Efficient Communication Protocols for Deciding Edit Distance
• Improved Approximation for Fréchet Distance on c-packed Curves Matching Conditional Lower Bounds
• Algorithms for Computing the Longest Parameterized Common Subsequence
• A fast algorithm for computing longest common subsequences
• Algorithms for the Longest Common Subsequence Problem
• Sparse dynamic programming I
• A Four Russians algorithm for regular expression pattern matching
• The String-to-String Correction Problem
• COMPUTING THE FRÉCHET DISTANCE BETWEEN TWO POLYGONAL CURVES
• The longest filled common subsequence problem
• Faster STR-IC-LCS Computation via RLE
• Longest Common Subsequences in Permutations and Maximum Cliques in Circle Graphs
• Streaming algorithms for embedding and computing edit distance in the low distance regime
• More Applications of the Polynomial Method to Algorithm Design
• Spelling correction in systems programs
• Space efficient streaming algorithms for the distance to monotonicity and asymmetric edit distance
• Weighted LCS

This page was built for publication: