Diverse Palindromic Factorization is NP-Complete

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

Research output: Contribution to journalArticlepeer-review

7 Citations (Scopus)


We prove that it is NP-complete to decide whether a given string can be factored into palindromes that are each unique in the factorization.

Original languageEnglish
Pages (from-to)143-163
Number of pages21
JournalInternational Journal of Foundations of Computer Science
Issue number2
Publication statusPublished - Feb 1 2018

All Science Journal Classification (ASJC) codes

  • Computer Science (miscellaneous)


Dive into the research topics of 'Diverse Palindromic Factorization is NP-Complete'. Together they form a unique fingerprint.

Cite this