Read networks and k-laminar graphs

Abstract : In this paper we introduce k-laminar graphs a new class of graphs which extends the idea of Asteroidal triple free graphs. Indeed a graph is k-laminar if it admits a diametral path that is k-dominating. This bio-inspired class of graphs was motivated by a biological application dealing with sequence similarity networks of reads (called hereafter read networks for short). We briefly develop the context of the biological application in which this graph class appeared and then we consider the relationships of this new graph class among known graph classes and then we study its recognition problem. For the recognition of k-laminar graphs, we develop polynomial algorithms when k is fixed. For k=1, our algorithm improves a Deogun and Krastch's algorithm (1999). We finish by an NP-completeness result when k is unbounded.
Type de document :
Pré-publication, Document de travail
2016
Liste complète des métadonnées

https://hal.inria.fr/hal-01282715
Contributeur : Michel Habib <>
Soumis le : vendredi 4 mars 2016 - 11:27:42
Dernière modification le : jeudi 3 mai 2018 - 13:42:15

Lien texte intégral

Identifiants

  • HAL Id : hal-01282715, version 1
  • ARXIV : 1603.01179

Citation

Finn Völkel, Eric Bapteste, Michel Habib, Philippe Lopez, Chloe Vigliotti. Read networks and k-laminar graphs. 2016. 〈hal-01282715〉

Partager

Métriques

Consultations de la notice

253