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

Christophe Crespelle 1, * Philippe Gambette 2
* Corresponding author
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.
Document type :
Journal articles
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
Contributor : Philippe Gambette <>
Submitted on : Friday, April 2, 2010 - 4:44:18 PM
Last modification on : Friday, October 21, 2016 - 2:51:23 PM
Document(s) archivé(s) le : Monday, July 5, 2010 - 9:14:00 PM

File

2010CrespelleGambette.pdf
Files produced by the author(s)

Identifiers

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>

Share

Metrics

Record views

388

Document downloads

211