2006-10-31
Online routing in quasi-planar and quasi-polyhedral graphs
Publication
Publication
Presented at the
4th Annual IEEE International Conference on Pervasive Computing and Communications Workshops, PerCom Workshops 2006 (March 2006)
We address the problem of online route discovery for a class of graphs that can be embedded either in two or in three dimensional space. In two dimensions we propose the class of quasi-planar graphs and in three dimensions the class of quasi-polyhedral graphs. In both cases we provide a routing algorithm that guarantees delivery. Our algorithms need only "remember" the source and destination nodes and one (respectively, two) reference nodes. Moreover, we show that the quasi-planar routing algorithm is inherently flexible in its path-finding, and as an application demonstrate computational results for a network load problem.
| Additional Metadata | |
|---|---|
| Persistent URL | dx.doi.org/10.1109/PERCOMW.2006.107 |
| Conference | 4th Annual IEEE International Conference on Pervasive Computing and Communications Workshops, PerCom Workshops 2006 |
| Citation |
Kranakis, E, Mott, T. (Tim), & Stacho, L. (Ladislav). (2006). Online routing in quasi-planar and quasi-polyhedral graphs. Presented at the 4th Annual IEEE International Conference on Pervasive Computing and Communications Workshops, PerCom Workshops 2006. doi:10.1109/PERCOMW.2006.107
|