On the solution bound of two-sided scaffold filling

DOI10.1016/J.TCS.2021.04.024MaRDI QIDQ2034400zbMATH OpenOpenAlexFDO

Authors Jingjing Ma, Daming Zhu, Haitao Jiang, Binhai Zhu

Publication date 22 June 2021

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2021.04.024

zbMATH Keywords

computational complexitygenomeperformance ratioscaffold filling

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Algorithms on strings (68W32) Analysis of algorithms (68W40) Genetics and epigenetics (92D10)

Recommendations

• A 1.4-approximation algorithm for two-sided scaffold filling
• A 1.5-approximation algorithm for two-sided scaffold filling
• The algorithm for the two-sided scaffold filling problem
• Notes on the $$\frac{6}{5}$$ -Approximation Algorithm for One-Sided Scaffold Filling
• Approximation and nonapproximability for the one-sided scaffold filling problem

Cites work

• A 1.4-approximation algorithm for two-sided scaffold filling
• A 1.5-approximation algorithm for two-sided scaffold filling
• A polynomial time solution for permutation scaffold filling
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
• Filling Scaffolds with Gene Repetitions: Maximizing the Number of Adjacencies
• Fixed-parameter algorithms for scaffold filling
• Genomic scaffold filling revisited
• scientific article; zbMATH DE number 910871 (Why is no real title available?)
• scientific article; zbMATH DE number 7203332 (Why is no real title available?)
• Local optimality and its application on independent sets for \(k\)-claw free graphs
• Notes on the $$\frac{6}{5}$$ -Approximation Algorithm for One-Sided Scaffold Filling
• On the Approximability of Comparing Genomes with Duplicates
• On the inapproximability of the exemplar conserved interval distance problem of genomes
• The Approximability of the Exemplar Breakpoint Distance Problem
• The complexity of calculating exemplar distances
• The Exemplar Breakpoint Distance for Non-trivial Genomes Cannot Be Approximated
• The greedy path-merging algorithm for contig scaffolding

Cited in

(3)

• A 1.5-approximation algorithm for two-sided scaffold filling
• Notes on the \(\frac{6}{5}\)-approximation algorithm for one-sided scaffold filling
• A 1.4-approximation algorithm for two-sided scaffold filling

This page was built for publication: On the solution bound of two-sided scaffold filling

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2034400)