Approximation and Nonapproximability for the One-Sided Scaffold Filling Problem

DOI10.1007/978-3-319-21398-9_20zbMath1465.92070OpenAlexW1158677828MaRDI QIDQ3196388

Jingjing Ma, Haitao Jiang, Junfeng Luan, Daming Zhu

Publication date: 29 October 2015

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-21398-9_20

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Genetics and epigenetics (92D10) Approximation algorithms (68W25)

Related Items (3)

Genomic Scaffold Filling: A Progress Report ⋮ Notes on the $$\frac{6}{5}$$ -Approximation Algorithm for One-Sided Scaffold Filling ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Maximum bounded 3-dimensional matching is MAX SNP-complete
• On the inapproximability of the exemplar conserved interval distance problem of genomes
• Filling Scaffolds with Gene Repetitions: Maximizing the Number of Adjacencies
• Non-breaking Similarity of Genomes with Gene Repetitions
• The Exemplar Breakpoint Distance for Non-trivial Genomes Cannot Be Approximated
• On the Approximability of Comparing Genomes with Duplicates
• On Syntactic versus Computational Views of Approximability
• The Algorithm for the Two-Sided Scaffold Filling Problem
• The Approximability of the Exemplar Breakpoint Distance Problem
• Algorithms and Computation

This page was built for publication: Approximation and Nonapproximability for the One-Sided Scaffold Filling Problem