Minimal generators in optimal time

DOI10.4230/LIPICS.CPM.2025.14MaRDI QIDQ7299448zbMATH OpenFDO

Authors Jonas Ellert, Paweł Gawrychowski, Tatiana Starikovskaya

Publication date 17 July 2026

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.CPM.2025.14

Mathematics Subject Classification ID

Algorithms on strings (68W32)

Cites work

• A New Linear-Time ``On-Line Algorithm for Finding the Smallest Initial Palindrome of a String
• An O(n log n) algorithm for finding all repetitions in a string
• An optimal minimum spanning tree algorithm
• Data structures for range minimum queries in multidimensional arrays
• Fast Pattern Matching in Strings
• Faster queries for longest substring palindrome after block edit
• scientific article; zbMATH DE number 1256660 (Why is no real title available?)
• Lempel-Ziv factorization may be harder than computing all runs
• Linear computation of unbordered conjugate on unordered alphabet
• Linear time runs over general ordered alphabets
• Longest common substring made fully dynamic
• Longest Lyndon Substring After Edit
• LRM-trees: compressed indices, adaptive sorting, and compressed permutations
• Optimal square detection over general alphabets
• Problems in data structures and algorithms
• Repetition Detection in a Dynamic String
• Truly subcubic algorithms for language edit distance and RNA folding via fast bounded-difference min-plus product
• Walking on words

This page was built for publication: Minimal generators in optimal time

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