Computing equality-free and repetitive string factorisations

DOI10.1016/J.TCS.2016.01.006MaRDI QIDQ2634669zbMATH OpenOpenAlexFDO

Authors 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

multivariate algorithmicsNP-hard string problemsparameterised complexitystring factorisations

Mathematics Subject Classification ID

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

Recommendations

• Computing equality-free string factorisations
• Generic Algorithms for Factoring Strings
• Factorizing strings into repetitions
• Efficient parallel algorithms to test square-freeness and factorize strings
• The maximum equality-free string factorization problem: gaps vs. no gaps
• String factorisations with maximum or minimum dimension
• Enhanced string factoring from alphabet orderings
• scientific article; zbMATH DE number 7651108
• Off-line and on-line algorithms for closed string factorization
• Repetitions in strings: algorithms and combinatorics

Cites work

• Complexity of a Collision-Aware String Partition Problem and Its Relation to Oligo Design for Gene Synthesis
• Computing equality-free string factorisations
• Diverse Palindromic Factorization Is NP-complete
• Fast Pattern Matching in Strings
• scientific article; zbMATH DE number 3888913 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1024080 (Why is no real title available?)
• Multivariate algorithmics for NP-hard string problems
• On the exact block cover problem
• Parametrized complexity theory.
• Pattern matching with variables: fast algorithms and new hardness results
• The complexity of string partitioning

Cited in

(10)

• Efficient parallel algorithms to test square-freeness and factorize strings
• Enhanced string factoring from alphabet orderings
• String factorisations with maximum or minimum dimension
• Computing equality-free string factorisations
• The maximum equality-free string factorization problem: gaps vs. no gaps
• scientific article; zbMATH DE number 6819809 (Why is no real title available?)
• Diverse Palindromic Factorization is NP-Complete
• Generic Algorithms for Factoring Strings
• Factorizing a String into Squares in Linear Time
• scientific article; zbMATH DE number 7740932 (Why is no real title available?)

This page was built for publication: Computing equality-free and repetitive string factorisations

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