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

Mathias Weller 1, 2 Annie Château 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.
Type de document :
Communication dans un congrès
COCOA: Combinatorial Optimization and Applications, Dec 2015, Houston, United States. COCOA 2015 - The 9th Annual International Conference on Combinatorial Optimization and Applications 9486, pp.409-423, 2015, LNCS. 〈10.1007/978-3-319-26626-8_30〉
Liste complète des métadonnées
https://hal-lirmm.ccsd.cnrs.fr/lirmm-01250982
Contributeur : Rodolphe Giroudeau <>
Soumis le : mardi 5 janvier 2016 - 14:48:04
Dernière modification le : jeudi 24 mai 2018 - 15:59:22

Identifiants

Collections

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

Citation

Mathias Weller, Annie Château, Rodolphe Giroudeau. On the Complexity of Scaffolding Problems: From Cliques to Sparse Graphs. COCOA: Combinatorial Optimization and Applications, Dec 2015, Houston, United States. COCOA 2015 - The 9th Annual International Conference on Combinatorial Optimization and Applications 9486, pp.409-423, 2015, LNCS. 〈10.1007/978-3-319-26626-8_30〉. 〈lirmm-01250982〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

130

Contact

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