On the Complexity of Scaffolding Problems: From Cliques to Sparse Graphs - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Communication Dans Un Congrès Année : 2015

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

Résumé

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.
Fichier non déposé

Dates et versions

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

Identifiants

Citer

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⟩
236 Consultations
0 Téléchargements

Altmetric

Partager

More