Diverse Palindromic Factorization Is NP-complete

DOI10.1007/978-3-319-21500-6_6zbMath1386.68063arXiv1503.04045OpenAlexW1744679373MaRDI QIDQ3451091

Travis Gagie, Simon J. Puglisi, Marcin Piątkowski, Shiho Sugimoto, Juha Kärkkäinen, Hideo Bannai, Shunsuke Inenaga, Dominik Kempa

Publication date: 10 November 2015

Published in: Developments in Language Theory (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1503.04045

Mathematics Subject Classification ID

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

Related Items (7)

Palindromic factorization of rich words ⋮ Computing equality-free and repetitive string factorisations ⋮ Computing Equality-Free String Factorisations ⋮ Algorithms and combinatorial properties on shortest unique palindromic substrings ⋮ Counting Palindromes in Substrings ⋮ Diverse Palindromic Factorization is NP-Complete ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• On palindromic factorization of words
• A subquadratic algorithm for minimum palindromic factorization
• A universal algorithm for sequential data compression
• Compression of individual sequences via variable-rate coding
• On the palindromic decomposition of binary words
• Computing Palindromic Factorizations and Palindromic Covers On-line

This page was built for publication: Diverse Palindromic Factorization Is NP-complete