Unrestricted and complete Breadth-First Search of trapezoid graphs in O(n) time

Christophe Crespelle 1, * Philippe Gambette 2
* Auteur correspondant
1 ComplexNetworks
LIP6 - Laboratoire d'Informatique de Paris 6
2 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : We present an O(n) Breadth-First Search algorithm for trapezoid graphs, which takes as input a trapezoid model and any priority order on the vertices. Our algorithm is the first able to produce any BFS-tree, and not only one specific to the model given as input, within this complexity. Moreover, it produces all the shortest paths from the root of the BFS-tree to the other vertices of the graph.
Type de document :
Article dans une revue
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00469844
Contributeur : Philippe Gambette <>
Soumis le : vendredi 2 avril 2010 - 16:44:18
Dernière modification le : jeudi 21 mars 2019 - 14:37:52
Document(s) archivé(s) le : lundi 5 juillet 2010 - 21:14:00

Fichier

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

Identifiants

Citation

Christophe Crespelle, Philippe Gambette. Unrestricted and complete Breadth-First Search of trapezoid graphs in O(n) time. Information Processing Letters, Elsevier, 2010, 110, pp.497-502. ⟨10.1016/j.ipl.2010.03.015⟩. ⟨lirmm-00469844⟩

Partager

Métriques

Consultations de la notice

602

Téléchargements de fichiers

270