Faculty of Graduate Studies (Electronic Theses and Practica)

Permanent URI for this community

http://hdl.handle.net/1993/5
This community holds theses prepared by graduate students and reviewed by program advisors.

Browse

Browsing Faculty of Graduate Studies (Electronic Theses and Practica) by Subject "1-bit memory local routing algorithm"

Now showing 1 - 1 of 1
  • Thumbnail Image
    Item
    Open Access
    Local geometric routing algorithms for edge-augmented planar graphs
    (2013-09-20) Wahid, Mohammad Abdul; Young, Jim (Computer Science) Bose, Prosenjit (Carleton University); Durocher, Stephane (Computer Science)
    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).