 |
 |
|
|
| HAL: lirmm-00469844, version 1 |
| DOI: 10.1016/j.ipl.2010.03.015 |
| Detailed view |  Export this paper |
|
|
| 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] |
|
|
|
|
| Subject | : | Computer Science/Data Structures and Algorithms |
|
|
| Breadth-First Search – Trapezoid graphs – Permutation graphs – Interval graphs – Shortest paths – Graph algorithms |
|
|
|
| Attached file list to this document: | |||||
|
|||||
|
|
|
| lirmm-00469844, version 1 | |
| http://hal-lirmm.ccsd.cnrs.fr/lirmm-00469844 | |
| oai:hal-lirmm.ccsd.cnrs.fr:lirmm-00469844 | |
| From: Algo Ligm | |
| Submitted on: Friday, 2 April 2010 16:44:18 | |
| Updated on: Friday, 14 May 2010 12:05:50 | |
