| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 428004 | Information Processing Letters | 2010 | 6 Pages |
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.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
