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.
Complete list of metadatas

Cited literature [11 references]  Display  Hide  Download

https://hal.inria.fr/inria-00471610
Contributor : Laurent Viennot <>
Submitted on : Thursday, April 8, 2010 - 4:13:34 PM
Last modification on : Friday, January 4, 2019 - 5:33:25 PM
Long-term archiving on : Friday, July 9, 2010 - 9:17:56 PM

Files

ami96.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00471610, version 1

Citation

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

Share

Metrics

Record views

228

Files downloads

2081