Diverse Palindromic Factorization is NP-Complete

DOI10.1142/S0129054118400014zbMath1387.68119WikidataQ129997400 ScholiaQ129997400MaRDI QIDQ4640035

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

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

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

Related Items (4)

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

Uses Software

• EERTREE

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On palindromic factorization of words
• A subquadratic algorithm for minimum palindromic factorization
• EERTREE: an efficient data structure for processing palindromes in strings
• The smallest grammar problem revisited
• Computing equality-free and repetitive string factorisations
• Unshuffling a square is NP-hard
• Diverse Palindromic Factorization Is NP-complete
• A universal algorithm for sequential data compression
• Compression of individual sequences via variable-rate coding
• On the Complexity of Grammar-Based Compression over Fixed Alphabets
• On the palindromic decomposition of binary words
• Palindromic length in linear time
• Computing Palindromic Factorizations and Palindromic Covers On-line
• Pal k is Linear Recognizable Online
• Tight Tradeoffs for Real-Time Approximation of Longest Palindromes in Streams.

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