Better Approximation Algorithms for Scaffolding Problems

DOI10.1007/978-3-319-39817-4_3zbMath1475.68466OpenAlexW2490176763MaRDI QIDQ4632165

Zhi-Zhong Chen, Lusheng Wang, Youta Harada, Fei Guo, Eita MacHida

Publication date: 26 April 2019

Published in: Frontiers in Algorithmics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-39817-4_3

zbMATH Keywords

matchingsapproximation algorithmsrandomized algorithmsscaffolding

Mathematics Subject Classification ID

Genetics and epigenetics (92D10) Approximation algorithms (68W25) Randomized algorithms (68W20) Computational methods for problems pertaining to biology (92-08) Algorithms on strings (68W32)

Uses Software

• ScaffMatch

Cites Work

• An approximation algorithm for the maximum traveling salesman problem
• A complexity and approximation framework for the maximization scaffolding problem
• On the Complexity of Scaffolding Problems: From Cliques to Sparse Graphs
• The Traveling Salesman Problem with Distances One and Two

This page was built for publication: Better Approximation Algorithms for Scaffolding Problems