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
Information Processing Letters, Elsevier, 2010, 110, pp.497-502. <10.1016/j.ipl.2010.03.015>
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 : vendredi 21 octobre 2016 - 14:51:23
Document(s) archivé(s) le : lundi 5 juillet 2010 - 21:14:00

Fichier

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

Identifiants

Collections

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

388

Téléchargements du document

211