On the approximability of the simplified partial digest problem

DOI10.1016/j.dam.2009.04.017zbMath1229.90282OpenAlexW2064776523WikidataQ57387743 ScholiaQ57387743MaRDI QIDQ967421

Marta Kasprzak, Alexandr Kovalev, Mikhail Y. Kovalyov, Jacek Błażewicz, Edmund Kieran Burke

Publication date: 28 April 2010

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2009.04.017

zbMATH Keywords

computational complexityapproximationgenome mappingsimplified partial digest problem

Mathematics Subject Classification ID

Applications of mathematical programming (90C90) Approximation methods and heuristics in mathematical programming (90C59)

Related Items (1)

A new dynamic programming algorithm for the simplified partial digest problem

Cites Work

• The simplified partial digest problem: approximation and a graph-theoretic model
• A partial digest approach to restriction site mapping
• Some necessary clarifications about the chords' problem and the partial digest problem
• Combinatorial optimization in DNA mapping — a computational thread of the Simplified Partial Digest Problem
• LATIN 2004: Theoretical Informatics
• The NP-completeness column: An ongoing guide
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: On the approximability of the simplified partial digest problem