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

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

10 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 languageEnglish
Title of host publicationDevelopments in Language Theory - 19th International Conference, DLT 2015, Proceedings
PublisherSpringer Verlag
Pages85-96
Number of pages12
ISBN (Print)9783319214993
DOIs
Publication statusPublished - 1 Jan 2015
MoE publication typeA4 Article in a conference publication
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 (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume9168
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

ConferenceInternational Conference on Developments in Language Theory
Abbreviated titleDLT
Country/TerritoryUnited Kingdom
CityLiverpool
Period27/07/201530/07/2015

Fingerprint

Dive into the research topics of 'Diverse palindromic factorization is NP-complete'. Together they form a unique fingerprint.

Cite this