Tractability and Approximability of Maximal Strip Recovery

DOI10.1007/978-3-642-21458-5_29zbMath1339.92050OpenAlexW2178400436MaRDI QIDQ3011866

Irena Rusu, Laurent Bulteau, Guillaume Fertin, Ming-Hui Jiang

Publication date: 29 June 2011

Published in: Combinatorial Pattern Matching (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-21458-5_29

zbMATH Keywords

FPT algorithmcomparative genomicsmaximal strip recovery

Mathematics Subject Classification ID

Genetics and epigenetics (92D10) Approximation algorithms (68W25)

Related Items

Maximal strip recovery problem with gaps: hardness and approximation algorithms ⋮ Inapproximability of maximal strip recovery

Cites Work

• Unnamed Item
• Exact and approximation algorithms for the complementary maximal strip recovery problem
• On recovering syntenic blocks from comparative maps
• On the Parameterized Complexity of Some Optimization Problems Related to Multiple-Interval Graphs
• Efficient Exact and Approximate Algorithms for the Complement of Maximal Strip Recovery
• Inapproximability of Maximal Strip Recovery: II
• On the Tractability of Maximal Strip Recovery
• Maximal Strip Recovery Problem with Gaps: Hardness and Approximation Algorithms