Computing equality-free and repetitive string factorisations

DOI10.1016/j.tcs.2016.01.006zbMath1335.68107OpenAlexW2238855891MaRDI QIDQ2634669

Markus L. Schmid

Publication date: 18 February 2016

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2016.01.006

zbMATH Keywords

parameterised complexitymultivariate algorithmicsNP-hard string problemsstring factorisations

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorics on words (68R15)

Related Items

The Maximum Equality-Free String Factorization Problem: Gaps vs. No Gaps, Diverse Palindromic Factorization is NP-Complete, String factorisations with maximum or minimum dimension

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The complexity of string partitioning
• Parametrized complexity theory.
• Computing Equality-Free String Factorisations
• Diverse Palindromic Factorization Is NP-complete
• Complexity of a Collision-Aware String Partition Problem and Its Relation to Oligo Design for Gene Synthesis
• Fast Pattern Matching in Strings
• On the Exact Block Cover Problem