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

Mathias Weller 1, 2 Annie Chateau 1 Rodolphe Giroudeau 3
1 MAB - Méthodes et Algorithmes pour la Bioinformatique
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
2 IBC - Institut de Biologie Computationnelle
3 MAORE - Méthodes Algorithmes pour l'Ordonnancement et les Réseaux
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
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.
Document type :
Conference papers
Complete list of metadatas
https://hal-lirmm.ccsd.cnrs.fr/lirmm-01250982
Contributor : Rodolphe Giroudeau <>
Submitted on : Tuesday, January 5, 2016 - 2:48:04 PM
Last modification on : Friday, March 15, 2019 - 5:02:19 PM

Identifiers

Collections

INRA | INRIA | MAORE | MAB | IBC | LIRMM | MIPS | UNIV-MONTPELLIER

Citation

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⟩

Export

BibTeX TEI DC DCterms EndNote

Share

Metrics

Record views

245

Contact

support.ccsd.cnrs.fr
hal.support@ccsd.cnrs.fr
Logo CCSD