Diverse Palindromic Factorization is NP-Complete
From MaRDI portal
Publication:4640035
DOI10.1142/S0129054118400014zbMATH Open1387.68119WikidataQ129997400 ScholiaQ129997400MaRDI QIDQ4640035FDOQ4640035
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)
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Combinatorics on words (68R15)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Compression of individual sequences via variable-rate coding
- A universal algorithm for sequential data compression
- On the complexity of grammar-based compression over fixed alphabets
- On palindromic factorization of words
- On the palindromic decomposition of binary words
- Unshuffling a square is NP-hard
- A subquadratic algorithm for minimum palindromic factorization
- Title not available (Why is that?)
- Computing palindromic factorizations and palindromic covers on-line
- \(\mathrm{Pal}^{k}\) is linear recognizable online
- Palindromic length in linear time
- Pattern matching with variables: fast algorithms and new hardness results
- Computing equality-free and repetitive string factorisations
- The smallest grammar problem revisited
- Tight Tradeoffs for Real-Time Approximation of Longest Palindromes in Streams.
- Diverse Palindromic Factorization Is NP-complete
Cited In (5)
Uses Software
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)
