Diverse Palindromic Factorization is NP-Complete

DOI10.1142/S0129054118400014MaRDI QIDQ4640035zbMATH OpenWikidataFDO

Authors Hideo Bannai, Travis Gagie, Shunsuke Inenaga, Juha Kärkkäinen, Dominik Kempa, Marcin Piatkowski, Shiho Sugimoto

Publication date 15 May 2018

Published in International Journal of Foundations of Computer Science (Search for Journal in Brave)

zbMATH Keywords

palindromesstring factorizationNP-complete problems on strings

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Combinatorics on words (68R15)

Cites work

• scientific article; zbMATH DE number 3489106 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 3325539 (Why is no real title available?)
• A subquadratic algorithm for minimum palindromic factorization
• A universal algorithm for sequential data compression
• Compression of individual sequences via variable-rate coding
• Computing equality-free and repetitive string factorisations
• Computing palindromic factorizations and palindromic covers on-line
• Diverse Palindromic Factorization Is NP-complete
• On palindromic factorization of words
• On the complexity of grammar-based compression over fixed alphabets
• On the palindromic decomposition of binary words
• Palindromic length in linear time
• Pattern matching with variables: fast algorithms and new hardness results
• The smallest grammar problem revisited
• Tight Tradeoffs for Real-Time Approximation of Longest Palindromes in Streams.
• Unshuffling a square is NP-hard
• \(\mathrm{Pal}^{k}\) is linear recognizable online

Cited in

(5)

• On the size of overlapping Lempel-Ziv and Lyndon factorizations
• A subquadratic algorithm for minimum palindromic factorization
• Factorizing strings into repetitions
• On highly palindromic words: the ternary case
• Palindromic trees for a sliding window and its applications

Describes a project that uses

Uses Software

• EERTREE

This page was built for publication: Diverse Palindromic Factorization is NP-Complete

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