Unrestricted and complete Breadth-First Search of trapezoid graphs in O(n) time - Archive ouverte HAL Accéder directement au contenu
Article Dans Une Revue Information Processing Letters Année : 2010

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

(1) , (2)
1
2
Christophe Crespelle
  • Fonction : Auteur correspondant
  • PersonId : 863155

Connectez-vous pour contacter l'auteur

Résumé

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.
Fichier principal
Vignette du fichier
2010CrespelleGambette.pdf (253.17 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

lirmm-00469844 , version 1 (02-04-2010)

Identifiants

Citer

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

Altmetric

Partager

Gmail Facebook Twitter LinkedIn More