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

*Tämän työn vastaava kirjoittaja

Tutkimustuotos: Artikkeli kirjassa/konferenssijulkaisussaConference contributionScientificvertaisarvioitu

10 Sitaatiot (Scopus)

Abstrakti

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.

AlkuperäiskieliEnglanti
OtsikkoDevelopments in Language Theory - 19th International Conference, DLT 2015, Proceedings
KustantajaSpringer Verlag
Sivut85-96
Sivumäärä12
ISBN (painettu)9783319214993
DOI - pysyväislinkit
TilaJulkaistu - 1 tammikuuta 2015
OKM-julkaisutyyppiA4 Artikkeli konferenssijulkaisuussa
TapahtumaInternational Conference on Developments in Language Theory - Liverpool, Iso-Britannia
Kesto: 27 heinäkuuta 201530 heinäkuuta 2015
Konferenssinumero: 19

Julkaisusarja

NimiLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Vuosikerta9168
ISSN (painettu)0302-9743
ISSN (elektroninen)1611-3349

Conference

ConferenceInternational Conference on Developments in Language Theory
LyhennettäDLT
Maa/AlueIso-Britannia
KaupunkiLiverpool
Ajanjakso27/07/201530/07/2015

Sormenjälki

Sukella tutkimusaiheisiin 'Diverse palindromic factorization is NP-complete'. Ne muodostavat yhdessä ainutlaatuisen sormenjäljen.

Siteeraa tätä