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

Christophe Paul; Laurent Viennot

Rapport (Rapport De Recherche) Année : 1997

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

(1) , (2)

1
2

Christophe Paul

Fonction : Auteur
PersonId : 4726
IdHAL : christophe-paul
ORCID : 0000-0001-6519-975X
IdRef : 151101345

Algorithmes, Graphes et Combinatoire

Laurent Viennot

Fonction : Auteur
PersonId : 1841
IdHAL : laurentviennot
IdRef : 034781072

Laboratoire Informatique Théorique et Programmation

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.

Domaines

Algorithme et structure de données [cs.DS] Calcul parallèle, distribué et partagé [cs.DC] Réseaux et télécommunications [cs.NI] Web

Fichier principal

ami96.pdf (199.08 Ko)

Origine : Fichiers produits par l'(les) auteur(s)

Laurent Viennot : Connectez-vous pour contacter le contributeur

https://inria.hal.science/inria-00471610

Soumis le : jeudi 8 avril 2010-16:13:34

Dernière modification le : vendredi 24 mars 2023-14:52:53

Archivage à long terme le : vendredi 9 juillet 2010-21:17:56

Dates et versions

inria-00471610 , version 1 (08-04-2010)

Identifiants

HAL Id : inria-00471610 , version 1

Citer

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

Exporter

BibTeX XML-TEI Dublin Core DC Terms EndNote DataCite

Collections

UNIV-PARIS7 UPMC CNRS ALGCO LIRMM LARA MIPS UNIV-MONTPELLIER SORBONNE-UNIVERSITE

180 Consultations

2974 Téléchargements

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

Résumé

Domaines

Dates et versions

Identifiants

Citer

Exporter

Collections

Partager