登入選單

返回Google圖書搜尋

Local Geometric Routing Algorithms for Edge-augmented Planar Graphs

Mohammad Abdul Wahid

出版	University of Manitoba, 2013
URL	http://books.google.com.hk/books?id=HpMajwEACAAJ&hl=&source=gbs_api

註釋

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).