On the solution bound of two-sided scaffold filling

DOI10.1016/j.tcs.2021.04.024zbMath1504.68296OpenAlexW3158152626MaRDI QIDQ2034400

Haitao Jiang, Daming Zhu, Jingjing Ma, 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 complexityperformance ratiogenomescaffold filling

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A 1.5-approximation algorithm for two-sided scaffold filling
• Local optimality and its application on independent sets for \(k\)-claw free graphs
• On the inapproximability of the exemplar conserved interval distance problem of genomes
• Fixed-parameter algorithms for scaffold filling
• A Polynomial Time Solution for Permutation Scaffold Filling
• Filling Scaffolds with Gene Repetitions: Maximizing the Number of Adjacencies
• The greedy path-merging algorithm for contig scaffolding
• The Exemplar Breakpoint Distance for Non-trivial Genomes Cannot Be Approximated
• On the Approximability of Comparing Genomes with Duplicates
• Notes on the $$\frac{6}{5}$$ -Approximation Algorithm for One-Sided Scaffold Filling
• A 1.4-Approximation Algorithm for Two-Sided Scaffold Filling
• Genomic Scaffold Filling Revisited.
• The Approximability of the Exemplar Breakpoint Distance Problem
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs

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