The Approximability of the Exemplar Breakpoint Distance Problem

DOI10.1007/11775096_27zbMath1137.92336MaRDI QIDQ5434407

Zhixiang Chen, Binhai Zhu, Bin Fu

Publication date: 4 January 2008

Published in: Algorithmic Aspects in Information and Management (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/11775096_27

Mathematics Subject Classification ID

68W40: Analysis of algorithms

92D10: Genetics and epigenetics

68W25: Approximation algorithms

92-08: Computational methods for problems pertaining to biology

Related Items

Genomic Scaffold Filling: A Progress Report, Notes on the $$\frac{6}{5}$$ -Approximation Algorithm for One-Sided Scaffold Filling, Can a Breakpoint Graph be Decomposed into None Other Than 2-Cycles?, A Retrospective on Genomic Preprocessing for Comparative Genomics, On the Approximability of Comparing Genomes with Duplicates, Simplifying 3D Polygonal Chains Under the Discrete Fréchet Distance, A 1.5-approximation algorithm for two-sided scaffold filling, On the approximability of the exemplar adjacency number problem for genomes with gene repetitions, Approximating multilinear monomial coefficients and maximum multilinear monomials in multivariate polynomials, On the solution bound of two-sided scaffold filling, A new approximation algorithm for contig-based genomic scaffold filling, On the inapproximability of the exemplar conserved interval distance problem of genomes, Can a breakpoint graph be decomposed into none other than 2-cycles?, Filling Scaffolds with Gene Repetitions: Maximizing the Number of Adjacencies, Approximation and Nonapproximability for the One-Sided Scaffold Filling Problem, The Exemplar Breakpoint Distance for Non-trivial Genomes Cannot Be Approximated