Tight Tradeoffs for Real-Time Approximation of Longest Palindromes in Streams.
From MaRDI portal
Publication:5369553
DOI10.4230/LIPIcs.CPM.2016.18zbMath1380.68475arXiv1610.03125OpenAlexW2531422270MaRDI QIDQ5369553
Przemysław Uznański, Oleg Merkurev, Paweł Gawrychowski, Arseny M. Shur
Publication date: 17 October 2017
Full work available at URL: https://arxiv.org/abs/1610.03125
Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Randomized algorithms (68W20) Algorithms on strings (68W32)
Related Items
Unnamed Item, Computing longest palindromic substring after single-character or block-wise edits, Diverse Palindromic Factorization is NP-Complete, Searching Long Repeats in Streams, Faster queries for longest substring palindrome after block edit, Unnamed Item, Tight tradeoffs for real-time approximation of longest palindromes in streams