 |
HAL-LIRMM - Open Archive |  |
Conference papers
New Polynomial-Time Algorithm around the Scaffolding Problem
Abstract : We describe in this paper an approximation algorithm for the scaffolding problem, which is part of genome inference in bioinformatics. The aim of the problem is to find a maximum weighted collection of disjoint alternating cycles and paths covering a particular graph called scaffold graph. The problem is known to be NP-complete, and we describe further result concerning a special class of graphs aiming to be close to real instances. The described algorithm is the first polynomial-time approximation algorithm designed for this problem on non-complete graphs.
Cited literature [10 references]
https://hal-lirmm.ccsd.cnrs.fr/lirmm-02047701
Contributor : Tom Davot <>
Submitted on : Monday, February 25, 2019 - 10:52:33 AM
Last modification on : Thursday, May 14, 2020 - 9:12:02 AM
Long-term archiving on: : Sunday, May 26, 2019 - 1:16:19 PM
Contributor : Tom Davot <>
Submitted on : Monday, February 25, 2019 - 10:52:33 AM
Last modification on : Thursday, May 14, 2020 - 9:12:02 AM
Long-term archiving on: : Sunday, May 26, 2019 - 1:16:19 PM
File
main.pdf
Files produced by the author(s)