HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Reports

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 metadata

Cited literature [11 references]  Display  Hide  Download

https://hal.inria.fr/inria-00471610
Contributor : Laurent Viennot Connect in order to contact the contributor
Submitted on : Thursday, April 8, 2010 - 4:13:34 PM
Last modification on : Friday, November 19, 2021 - 6:06:06 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

170

Files downloads

2870