 |
 |
|
|
| HAL : lirmm-00469844, version 1 |
| DOI : 10.1016/j.ipl.2010.03.015 |
| Fiche détaillée |  Récupérer au format |
|
|
| Information Processing Letters 110 (2010) 497-502 |
|
|
|
|
| Unrestricted and complete Breadth-First Search of trapezoid graphs in O(n) time |
|
|
Christophe Crespelle 1Philippe Gambette 2 |
|
|
| (2010) |
|
|
|
| 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. |
|
|
|
|
|
|
|
|
|
|
|
| 1 : | Laboratoire d'Informatique de Paris 6 (LIP6) |
|
|
|
CNRS : UMR7606 – Université Paris VI - Pierre et Marie Curie |
|
|
| 2 : | Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier (LIRMM) |
|
|
|
CNRS : UMR5506 – Université Montpellier II - Sciences et Techniques du Languedoc |
|
|
|
|
|
|
|
|
|
| [INFO/ALGCO] |
|
|
|
|
| Domaine | : | Informatique/Algorithme et structure de données |
|
|
| Breadth-First Search – Trapezoid graphs – Permutation graphs – Interval graphs – Shortest paths – Graph algorithms |
|
|
|
| Liste des fichiers attachés à ce document : | |||||
|
|||||
|
|
|
| lirmm-00469844, version 1 | |
| http://hal-lirmm.ccsd.cnrs.fr/lirmm-00469844 | |
| oai:hal-lirmm.ccsd.cnrs.fr:lirmm-00469844 | |
| Contributeur : Algo Ligm | |
| Soumis le : Vendredi 2 Avril 2010, 16:44:18 | |
| Dernière modification le : Vendredi 14 Mai 2010, 12:05:50 | |
