Paper Info
Title
Minimum Common String Partition Parameterized
Abstract
Minimum Common String Partition (MCSP) and related problems are of interest in, e.g., comparative genomics, DNA fingerprint assembly, and ortholog assignment. Given two strings with equal symbol content, the problem is to partition one string into kblocks, kas small as possible, and to permute them so as to obtain the other string. MCSP is NP-hard, and only approximation algorithms are known. Here we show that MCSP is fixed-parameter tractable in suitable parameters, so that practical instances can be efficiently solved to optimality.
Year
DOI
Venue
2008
10.1007/978-3-540-87361-7_8
WABI
Keywords
Field
DocType
fixed-parameter tractable,comparative genomics,dna fingerprint assembly,suitable parameter,minimum common string partition,related problem,equal symbol content,approximation algorithm,ortholog assignment,practical instance,dna fingerprinting
Discrete mathematics,Approximation algorithm,Combinatorics,Parameterized complexity,Permutation,Genome rearrangement,Greedy algorithm,Partition (number theory),Mathematics,Parameterized algorithms
Conference
Volume
ISSN
Citations 
5251
0302-9743
12
PageRank 
References 
Authors
0.85
9
1
Name
Order
Citations
PageRank
Peter Damaschke147156.99