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

doi:10.1007/978-3-319-21500-6_6

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 proceeding › Conference contribution › Scientific › peer-review

Original language	English
Title of host publication	Developments in Language Theory : 19th International Conference, DLT 2015, Liverpool, UK, July 27-30, 2015, Proceedings
Editors	Igor Potapov
Number of pages	12
Place of Publication	Cham
Publisher	Springer International Publishing AG
Publication date	2015
Pages	85-96
ISBN (Print)	978-3-319-21499-3
ISBN (Electronic)	978-3-319-21500-6
DOIs	https://doi.org/10.1007/978-3-319-21500-6_6
Publication status	Published - 2015
MoE publication type	A4 Article in conference proceedings
Event	International Conference on Developments in Language Theory - Liverpool, United Kingdom Duration: 27 Jul 2015 → 30 Jul 2015 Conference number: 19

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer
Volume	9168
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Fields of Science

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

Access to Document

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

Cite this

Bannai, H., Gagie, T., Inenaga, S., Kärkkäinen, J. T., Kempa, D., Piątkowski, M., Puglisi, S. J., & 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). Springer International Publishing AG. https://doi.org/10.1007/978-3-319-21500-6_6

@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{\c a}tkowski and Puglisi, {Simon John} and Shiho Sugimoto",

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",

note = "International Conference on Developments in Language Theory ; Conference date: 27-07-2015 Through 30-07-2015",

}

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 et al.
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 proceeding › Conference contribution › Scientific › peer-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 - Conference code: 19

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

T2 - International Conference on Developments in Language Theory

Y2 - 27 July 2015 through 30 July 2015

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). doi: 10.1007/978-3-319-21500-6_6