A Lower Bound for Jumbled Indexing

DOI10.1137/1.9781611975994.36MaRDI QIDQ5146803zbMATH OpenOpenAlexFDO

Authors Peyman Afshani, Ingo van Duijn, Rasmus Killmann, Jesper Sindahl Nielsen

Publication date 2 February 2021

Published in Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/1.9781611975994.36

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Cited in

(5)

• Generating a Gray code for prefix normal words in amortized polylogarithmic time per word
• On infinite prefix normal words
• Gapped string indexing in subquadratic space and sublinear query time
• Binary jumbled pattern matching: suffix tree indexing
• Binary jumbled indexing: suffix tree histogram

This page was built for publication: A Lower Bound for Jumbled Indexing

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