Complexity and Polynomial-Time Approximation Algorithms around the Scaffolding Problem

Annie Château 1 Rodolphe Giroudeau 2
1 MAB - Méthodes et Algorithmes pour la Bioinformatique
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
2 MAORE - Méthodes Algorithmes pour l'Ordonnancement et les Réseaux
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : We explore in this paper some complexity issues inspired by the contig scaffolding problem in bioinformatics. We focus on the following problem: given an undirected graph with no loop, and a perfect matching on this graph, find a set of cycles and paths covering every vertex of the graph, with edges alternatively in the matching and outside the matching, and satisfying a given constraint on the numbers of cycles and paths. We show that this problem is NP-complete, even in bipartite graphs. We also exhibit non-approximability and polynomial-time approximation results, in the optimization versions of the problem.
Type de document :
Communication dans un congrès
Dediu, Adrian-Horia; Martín-Vide, Carlos; Truthe, Bianca. AlCoB: Algorithms for Computational Biology, Jul 2014, Tarragona, Spain. Springer International Publishing, First International Conference, AlCoB 2014, Tarragona, Spain, July 1-3, 2014, Proceedigns, LNCS (8542), pp.47-58, 2014, Algorithms for Computational Biology. <http://grammars.grlmc.com/alcob2014/>. <10.1007/978-3-319-07953-0_4>
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01007556
Contributeur : Annie Chateau <>
Soumis le : lundi 16 juin 2014 - 18:26:47
Dernière modification le : vendredi 9 juin 2017 - 10:40:59

Identifiants

Collections

Citation

Annie Château, Rodolphe Giroudeau. Complexity and Polynomial-Time Approximation Algorithms around the Scaffolding Problem. Dediu, Adrian-Horia; Martín-Vide, Carlos; Truthe, Bianca. AlCoB: Algorithms for Computational Biology, Jul 2014, Tarragona, Spain. Springer International Publishing, First International Conference, AlCoB 2014, Tarragona, Spain, July 1-3, 2014, Proceedigns, LNCS (8542), pp.47-58, 2014, Algorithms for Computational Biology. <http://grammars.grlmc.com/alcob2014/>. <10.1007/978-3-319-07953-0_4>. <lirmm-01007556>

Partager

Métriques

Consultations de la notice

110