Unrestricted and complete Breadth-First Search of trapezoid graphs in O(n) time - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier 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

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⟩
402 Consultations
308 Téléchargements

Altmetric

Partager

Gmail Mastodon Facebook X LinkedIn More