TU Berlin

Research Group Algorithmics and Computational ComplexityTalk 10.01.2013

isti-logo

Page Content

to Navigation

Minimum Common String Partition Parameterized by Partition Size is Fixed-Parameter Tractable

Dr. Christian Komusiewicz (TU Berlin)

The NP-hard Minimum Common String Partition problem has as input two strings x and y and asks whether x and y can each be partitioned into at most k substrings, called blocks, such that both partitions use exactly the same blocks in a different order. In this work, we present the first fixed-parameter algorithm for Minimum Common String Partition using only parameter k.

Date
Speaker
Location
Language
10.01.2013 16:15
Christian Komusiewicz
TEL 512
german/english

Back to the research colloquium site.

Navigation

Quick Access

Schnellnavigation zur Seite über Nummerneingabe