Diverse Palindromic Factorization is NP-Complete

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

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

Original languageEnglish
Title of host publicationDevelopments in Language Theory : 19th International Conference, DLT 2015, Liverpool, UK, July 27-30, 2015, Proceedings
EditorsIgor Potapov
Number of pages12
Place of PublicationCham
PublisherSpringer International Publishing AG
Publication date2015
Pages85-96
ISBN (Print)978-3-319-21499-3
ISBN (Electronic)978-3-319-21500-6
DOIs
Publication statusPublished - 2015
MoE publication typeA4 Article in conference proceedings
EventInternational Conference on Developments in Language Theory - Liverpool, United Kingdom
Duration: 27 Jul 201530 Jul 2015
Conference number: 19

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume9168
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Fields of Science

  • 113 Computer and information sciences
  • palindromes
  • factorization
  • unique factors
  • NP-complete

Cite this

Bannai, H., Gagie, T., Inenaga, S., Kärkkäinen, J. T., Kempa, D., Piątkowski, M., ... Sugimoto, S. (2015). Diverse Palindromic Factorization is NP-Complete. In I. Potapov (Ed.), Developments in Language Theory: 19th International Conference, DLT 2015, Liverpool, UK, July 27-30, 2015, Proceedings (pp. 85-96). (Lecture Notes in Computer Science; Vol. 9168). Cham: Springer International Publishing AG. https://doi.org/10.1007/978-3-319-21500-6_6
Bannai, Hideo ; Gagie, Travis ; Inenaga, Shunsuke ; Kärkkäinen, Juha Tapani ; Kempa, Dominik ; Piątkowski, Marcin ; Puglisi, Simon John ; Sugimoto, Shiho. / Diverse Palindromic Factorization is NP-Complete. Developments in Language Theory: 19th International Conference, DLT 2015, Liverpool, UK, July 27-30, 2015, Proceedings. editor / Igor Potapov. Cham : Springer International Publishing AG, 2015. pp. 85-96 (Lecture Notes in Computer Science).
@inproceedings{2ce1bf6cba174a5bb1934a5be0fbeb10,
title = "Diverse Palindromic Factorization is NP-Complete",
keywords = "113 Computer and information sciences, palindromes, factorization, unique factors, NP-complete",
author = "Hideo Bannai and Travis Gagie and Shunsuke Inenaga and K{\"a}rkk{\"a}inen, {Juha Tapani} and Dominik Kempa and Marcin Piątkowski and Puglisi, {Simon John} and Shiho Sugimoto",
note = "Volume: Proceeding volume:",
year = "2015",
doi = "10.1007/978-3-319-21500-6_6",
language = "English",
isbn = "978-3-319-21499-3",
series = "Lecture Notes in Computer Science",
publisher = "Springer International Publishing AG",
pages = "85--96",
editor = "Igor Potapov",
booktitle = "Developments in Language Theory",
address = "Switzerland",

}

Bannai, H, Gagie, T, Inenaga, S, Kärkkäinen, JT, Kempa, D, Piątkowski, M, Puglisi, SJ & Sugimoto, S 2015, Diverse Palindromic Factorization is NP-Complete. in I Potapov (ed.), Developments in Language Theory: 19th International Conference, DLT 2015, Liverpool, UK, July 27-30, 2015, Proceedings. Lecture Notes in Computer Science, vol. 9168, Springer International Publishing AG, Cham, pp. 85-96, International Conference on Developments in Language Theory, Liverpool, United Kingdom, 27/07/2015. https://doi.org/10.1007/978-3-319-21500-6_6

Diverse Palindromic Factorization is NP-Complete. / Bannai, Hideo; Gagie, Travis; Inenaga, Shunsuke; Kärkkäinen, Juha Tapani; Kempa, Dominik; Piątkowski, Marcin; Puglisi, Simon John; Sugimoto, Shiho.

Developments in Language Theory: 19th International Conference, DLT 2015, Liverpool, UK, July 27-30, 2015, Proceedings. ed. / Igor Potapov. Cham : Springer International Publishing AG, 2015. p. 85-96 (Lecture Notes in Computer Science; Vol. 9168).

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

TY - GEN

T1 - Diverse Palindromic Factorization is NP-Complete

AU - Bannai, Hideo

AU - Gagie, Travis

AU - Inenaga, Shunsuke

AU - Kärkkäinen, Juha Tapani

AU - Kempa, Dominik

AU - Piątkowski, Marcin

AU - Puglisi, Simon John

AU - Sugimoto, Shiho

N1 - Volume: Proceeding volume:

PY - 2015

Y1 - 2015

KW - 113 Computer and information sciences

KW - palindromes

KW - factorization

KW - unique factors

KW - NP-complete

U2 - 10.1007/978-3-319-21500-6_6

DO - 10.1007/978-3-319-21500-6_6

M3 - Conference contribution

SN - 978-3-319-21499-3

T3 - Lecture Notes in Computer Science

SP - 85

EP - 96

BT - Developments in Language Theory

A2 - Potapov, Igor

PB - Springer International Publishing AG

CY - Cham

ER -

Bannai H, Gagie T, Inenaga S, Kärkkäinen JT, Kempa D, Piątkowski M et al. Diverse Palindromic Factorization is NP-Complete. In Potapov I, editor, Developments in Language Theory: 19th International Conference, DLT 2015, Liverpool, UK, July 27-30, 2015, Proceedings. Cham: Springer International Publishing AG. 2015. p. 85-96. (Lecture Notes in Computer Science). https://doi.org/10.1007/978-3-319-21500-6_6