Quelques algorithmes linéaires de reconnaissance autour de Lex-BFS

Christophe Paul 1 Laurent Viennot 2
1 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Résumé : Nous présesentons dans cet article des algorithmes de reconnaissances pour différentes classes de graphes (co-triangulés, intervalles, convexes, ...) tous basés sur Lex-BFS. Ces algorithmes sont optimaux, linéaires en la taille du graphe, et simples : ils évitent l'utilisation des PQ-arbres et de la décomposition modulaire.
Liste complète des métadonnées

Littérature citée [11 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00471610
Contributeur : Laurent Viennot <>
Soumis le : jeudi 8 avril 2010 - 16:13:34
Dernière modification le : jeudi 24 mai 2018 - 15:59:22
Document(s) archivé(s) le : vendredi 9 juillet 2010 - 21:17:56

Fichiers

ami96.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00471610, version 1

Collections

Citation

Christophe Paul, Laurent Viennot. Quelques algorithmes linéaires de reconnaissance autour de Lex-BFS. [Rapport de recherche] 1997. 〈inria-00471610〉

Partager

Métriques

Consultations de la notice

188

Téléchargements de fichiers

1231