Diverse palindromic factorization is NP-complete

Hideo Bannai; Travis Gagie; Shunsuke Inenaga; Juha Kärkkäinen; Dominik Kempa; Marcin Piątkowski; Simon J. 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 Kärkkäinen, Dominik Kempa, Marcin Piątkowski, Simon J. Puglisi, Shiho Sugimoto

^*Corresponding author for this work

Department of Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Scientific › peer-review

12 Citations (Scopus)

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
Title of host publication	Developments in Language Theory - 19th International Conference, DLT 2015, Proceedings
Publisher	Springer
Pages	85-96
Number of pages	12
ISBN (Print)	9783319214993
DOIs	https://doi.org/10.1007/978-3-319-21500-6_6
Publication status	Published - 1 Jan 2015
MoE publication type	A4 Article in a conference publication
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 (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	9168
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	International Conference on Developments in Language Theory
Abbreviated title	DLT
Country/Territory	United Kingdom
City	Liverpool
Period	27/07/2015 → 30/07/2015

Access to Document

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

OpenUrl availability

Full text

Cite this

Bannai, H., Gagie, T., Inenaga, S., Kärkkäinen, J., Kempa, D., Piątkowski, M., Puglisi, S. J., & Sugimoto, S. (2015). Diverse palindromic factorization is NP-complete. In Developments in Language Theory - 19th International Conference, DLT 2015, Proceedings (pp. 85-96). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9168). Springer. https://doi.org/10.1007/978-3-319-21500-6_6

@inproceedings{f75d340e6ea543d6b5306ab063992c38,

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

author = "Hideo Bannai and Travis Gagie and Shunsuke Inenaga and Juha K{\"a}rkk{\"a}inen and Dominik Kempa and Marcin Pi{\c a}tkowski and Puglisi, {Simon J.} and Shiho Sugimoto",

year = "2015",

month = jan,

day = "1",

doi = "10.1007/978-3-319-21500-6_6",

language = "English",

isbn = "9783319214993",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer",

pages = "85--96",

booktitle = "Developments in Language Theory - 19th International Conference, DLT 2015, Proceedings",

address = "Germany",

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

}

Bannai, H, Gagie, T, Inenaga, S, Kärkkäinen, J, Kempa, D, Piątkowski, M, Puglisi, SJ & Sugimoto, S 2015, Diverse palindromic factorization is NP-complete. in Developments in Language Theory - 19th International Conference, DLT 2015, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 9168, Springer, 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, Proceedings. Springer, 2015. p. 85-96 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); 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

AU - Kempa, Dominik

AU - Piątkowski, Marcin

AU - Puglisi, Simon J.

AU - Sugimoto, Shiho

N1 - Conference code: 19

PY - 2015/1/1

Y1 - 2015/1/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.

UR - http://www.scopus.com/inward/record.url?scp=84947093056&partnerID=8YFLogxK

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

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

M3 - Conference contribution

AN - SCOPUS:84947093056

SN - 9783319214993

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 85

EP - 96

BT - Developments in Language Theory - 19th International Conference, DLT 2015, Proceedings

PB - Springer

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 J, Kempa D, Piątkowski M et al. Diverse palindromic factorization is NP-complete. In Developments in Language Theory - 19th International Conference, DLT 2015, Proceedings. Springer. 2015. p. 85-96. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-319-21500-6_6

Diverse palindromic factorization is NP-complete

Abstract

Publication series

Conference

Access to Document

OpenUrl availability

Other files and links

Fingerprint

Cite this