Return to search

Local geometric routing algorithms for edge-augmented planar graphs

Given a geometric graph G = (V,E), where V is the set of vertices and E is the set of edges and a source-target pair {s,t} is a subset of V, a local geometric routing algorithm seeks a route from s to t using only local neighborhood relationships. This thesis proposes a local geometric routing algorithm that uses only a single state bit as message overhead and guarantees delivery of messages in three different classes of edge-augmented planar graphs: convex subdivisions, quasi planar convex subdivisions (allow some augmented edges on a spanning convex subdivision) and 2-augmented triangulations (allow some augmented edges on a spanning triangulation). The proposed algorithm is origin oblivious (does not require the knowledge of the origin vertex s) and predecessor oblivious (does not require the knowledge of the predecessor vertex).

Identiferoai:union.ndltd.org:LACETR/oai:collectionscanada.gc.ca:MWU.1993/22200
Date20 September 2013
CreatorsWahid, Mohammad Abdul
ContributorsDurocher, Stephane (Computer Science), Young, Jim (Computer Science) Bose, Prosenjit (Carleton University)
Source SetsLibrary and Archives Canada ETDs Repository / Centre d'archives des thèses électroniques de Bibliothèque et Archives Canada
Detected LanguageEnglish

Page generated in 0.002 seconds