direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments

Es gibt keine deutsche Übersetzung dieser Webseite.

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.

Zusatzinformationen / Extras