Diverse Palindromic Factorization is NP-Complete

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

doi:10.1142/S0129054118400014

Diverse Palindromic Factorization is NP-Complete

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

Computer Science

Kyushu University
Universidad Diego Portales
University of Helsinki
Nicolaus Copernicus University in Toruń

Research output: Contribution to journal › Article › peer-review

9 Scopus citations

Abstract

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 language	English
Pages (from-to)	143-163
Number of pages	21
Journal	International Journal of Foundations of Computer Science
Volume	29
Issue number	2
DOIs	https://doi.org/10.1142/S0129054118400014
State	Published - Feb 1 2018

Keywords

NP-complete problems on strings
palindromes
string factorization

Access to Document

10.1142/S0129054118400014

Cite this

@article{967f3d59f11b443e84701c433a5df383,

title = "Diverse Palindromic Factorization is NP-Complete",

abstract = "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.",

keywords = "NP-complete problems on strings, palindromes, string factorization",

author = "Hideo Bannai and Travis Gagie and Shunsuke Inenaga and Juha K{\"a}rkk{\"a}inen and Dominik Kempa and Marcin Piakowski and Shiho Sugimoto",

note = "Publisher Copyright: {\textcopyright} 2018 World Scientific Publishing Company.",

year = "2018",

month = feb,

day = "1",

doi = "10.1142/S0129054118400014",

language = "English",

volume = "29",

pages = "143--163",

journal = "International Journal of Foundations of Computer Science",

issn = "0129-0541",

number = "2",

}

TY - JOUR

T1 - Diverse Palindromic Factorization is NP-Complete

AU - Bannai, Hideo

AU - Gagie, Travis

AU - Inenaga, Shunsuke

AU - Kärkkäinen, Juha

AU - Kempa, Dominik

AU - Piakowski, Marcin

AU - Sugimoto, Shiho

PY - 2018/2/1

Y1 - 2018/2/1

N2 - 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.

AB - 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.

KW - NP-complete problems on strings

KW - palindromes

KW - string factorization

UR - https://www.scopus.com/pages/publications/85045195640

U2 - 10.1142/S0129054118400014

DO - 10.1142/S0129054118400014

M3 - Article

AN - SCOPUS:85045195640

SN - 0129-0541

VL - 29

SP - 143

EP - 163

JO - International Journal of Foundations of Computer Science

JF - International Journal of Foundations of Computer Science

IS - 2

ER -

Diverse Palindromic Factorization is NP-Complete

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this