On the Complexity of Scaffolding Problems: From Cliques to Sparse Graphs - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Conference Papers Year : 2015

On the Complexity of Scaffolding Problems: From Cliques to Sparse Graphs

Abstract

This paper is devoted to new results about the scaffolding problem, an integral problem of genome inference in bioinformatics. The problem consists of finding a collection of disjoint cycles and paths covering a particular graph called the “scaffold graph”. We examine the difficulty and the approximability of the scaffolding problem in special classes of graphs, either close to trees, or very dense. We propose negative and positive results, exploring the frontier between difficulty and tractability of computing and/or approximating a solution to the problem.
No file

Dates and versions

lirmm-01250982 , version 1 (05-01-2016)

Identifiers

Cite

Mathias Weller, Annie Chateau, Rodolphe Giroudeau. On the Complexity of Scaffolding Problems: From Cliques to Sparse Graphs. COCOA: Conference on Combinatorial Optimization and Applications, Dec 2015, Houston, United States. pp.409-423, ⟨10.1007/978-3-319-26626-8_30⟩. ⟨lirmm-01250982⟩
235 View
0 Download

Altmetric

Share

More