Diverse Palindromic Factorization is NP-Complete

Hideo Bannai, Travis Gagie, Shunsuke Inenaga, Juha Karkkainen, Dominik Kempa, Marcin Piatkowski, Shiho Sugimoto

Research output: Contribution to journalArticleScientificpeer-review

Original languageEnglish
JournalInternational Journal of Foundations of Computer Science
Volume29
Issue number2
Pages (from-to)143-163
Number of pages21
ISSN0129-0541
DOIs
Publication statusPublished - Feb 2018
MoE publication typeA1 Journal article-refereed
EventInternational Conference on Developments in Language Theory - Liverpool, United Kingdom
Duration: 27 Jul 201530 Jul 2015
Conference number: 19

Bibliographical note

Revised and extended version of the paper selected from the 19th International Conference on Developments in Language Theory (DLT 2015).

Fields of Science

  • NP-complete problems on strings
  • string factorization
  • palindromes
  • COMPRESSION
  • ALGORITHM
  • 113 Computer and information sciences

Cite this

Bannai, Hideo ; Gagie, Travis ; Inenaga, Shunsuke ; Karkkainen, Juha ; Kempa, Dominik ; Piatkowski, Marcin ; Sugimoto, Shiho. / Diverse Palindromic Factorization is NP-Complete. In: International Journal of Foundations of Computer Science. 2018 ; Vol. 29, No. 2. pp. 143-163.
@article{a63dd75036684c0d9251e66a7cf34139,
title = "Diverse Palindromic Factorization is NP-Complete",
keywords = "NP-complete problems on strings, string factorization, palindromes, COMPRESSION, ALGORITHM, 113 Computer and information sciences",
author = "Hideo Bannai and Travis Gagie and Shunsuke Inenaga and Juha Karkkainen and Dominik Kempa and Marcin Piatkowski and Shiho Sugimoto",
note = "Revised and extended version of the paper selected from the 19th International Conference on Developments in Language Theory (DLT 2015).",
year = "2018",
month = "2",
doi = "10.1142/S0129054118400014",
language = "English",
volume = "29",
pages = "143--163",
journal = "International Journal of Foundations of Computer Science",
issn = "0129-0541",
publisher = "WORLD SCIENTIFIC PUBL CO PTE LTD",
number = "2",

}

Bannai, H, Gagie, T, Inenaga, S, Karkkainen, J, Kempa, D, Piatkowski, M & Sugimoto, S 2018, 'Diverse Palindromic Factorization is NP-Complete', International Journal of Foundations of Computer Science, vol. 29, no. 2, pp. 143-163. https://doi.org/10.1142/S0129054118400014

Diverse Palindromic Factorization is NP-Complete. / Bannai, Hideo; Gagie, Travis; Inenaga, Shunsuke; Karkkainen, Juha; Kempa, Dominik; Piatkowski, Marcin; Sugimoto, Shiho.

In: International Journal of Foundations of Computer Science, Vol. 29, No. 2, 02.2018, p. 143-163.

Research output: Contribution to journalArticleScientificpeer-review

TY - JOUR

T1 - Diverse Palindromic Factorization is NP-Complete

AU - Bannai, Hideo

AU - Gagie, Travis

AU - Inenaga, Shunsuke

AU - Karkkainen, Juha

AU - Kempa, Dominik

AU - Piatkowski, Marcin

AU - Sugimoto, Shiho

N1 - Revised and extended version of the paper selected from the 19th International Conference on Developments in Language Theory (DLT 2015).

PY - 2018/2

Y1 - 2018/2

KW - NP-complete problems on strings

KW - string factorization

KW - palindromes

KW - COMPRESSION

KW - ALGORITHM

KW - 113 Computer and information sciences

U2 - 10.1142/S0129054118400014

DO - 10.1142/S0129054118400014

M3 - Article

VL - 29

SP - 143

EP - 163

JO - International Journal of Foundations of Computer Science

JF - International Journal of Foundations of Computer Science

SN - 0129-0541

IS - 2

ER -