On the monotonicity of a data stream

DOI10.1007/s00493-014-3035-1zbMath1389.68037OpenAlexW2090968858MaRDI QIDQ1677498

Hossein Jowhari, Funda Ergün

Publication date: 10 November 2017

Published in: Combinatorica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00493-014-3035-1

zbMATH Keywords

monotonicityprobabilistic methodstreaming algorithmsinversions

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10) Algorithms on strings (68W32)

Related Items (2)

Space-Efficient Algorithms for Longest Increasing Subsequence ⋮ Space-efficient algorithms for longest increasing subsequence

Cites Work

• Unnamed Item
• Unnamed Item
• A note on randomized streaming space bounds for the longest increasing subsequence problem
• Tight Lower Bounds for Multi-pass Stream Computation Via Pass Elimination
• Longest increasing subsequences: from patience sorting to the Baik-Deift-Johansson theorem
• Communication Complexity
• Lower Bounds on Streaming Algorithms for Approximating the Length of the Longest Increasing Subsequence
• Estimating the distance to a monotone function
• Computing and Combinatorics
• Estimating the Longest Increasing Sequence in Polylogarithmic Time
• Space efficient streaming algorithms for the distance to monotonicity and asymmetric edit distance

This page was built for publication: On the monotonicity of a data stream