The communication and streaming complexity of computing the longest common and increasing subsequences

zbMATH Open1302.68142MaRDI QIDQ2934612FDOQ2934612

David P. Woodruff, Xiaoming Sun

Publication date: 18 December 2014

Recommendations

• Computing and Combinatorics
• Finding longest increasing and common subsequences in streaming data
• Lower bounds on streaming algorithms for approximating the length of the longest increasing subsequence
• A note on randomized streaming space bounds for the longest increasing subsequence problem
• Fast computation of a longest increasing subsequence and application

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Cited In (12)

• Title not available (Why is that?)
• Communication-Efficient Private Protocols for Longest Common Subsequence
• Fast and longest rollercoasters
• Computing and Combinatorics
• Streaming and query once space complexity of longest increasing subsequence
• Title not available (Why is that?)
• Estimating the Longest Increasing Sequence in Polylogarithmic Time
• Space-efficient algorithms for longest increasing subsequence
• On the monotonicity of a data stream
• Space-Efficient Algorithms for Longest Increasing Subsequence
• Compressed communication complexity of longest common prefixes
• Finding longest increasing and common subsequences in streaming data

This page was built for publication: The communication and streaming complexity of computing the longest common and increasing subsequences

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