Local geometric routing algorithms for edge-augmented planar graphs

Simple item page
dc.contributor.authorWahid, Mohammad Abdul
dc.contributor.examiningcommitteeYoung, Jim (Computer Science) Bose, Prosenjit (Carleton University)en_US
dc.contributor.supervisorDurocher, Stephane (Computer Science)en_US
dc.date.accessioned2013-09-20T17:09:00Z
dc.date.available2013-09-20T17:09:00Z
dc.date.issued2013-09-20
dc.degree.disciplineComputer Scienceen_US
dc.degree.levelMaster of Science (M.Sc.)en_US
dc.description.abstractGiven 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).en_US
dc.description.noteFebruary 2014en_US
dc.identifier.urihttp://hdl.handle.net/1993/22200
dc.language.isoengen_US
dc.rightsopen accessen_US
dc.subjectonline routing algorithmen_US
dc.subjectlocal routing algorithmen_US
dc.subjectgeometric routing algorithmen_US
dc.subjectdistributed routing algorithmen_US
dc.subjectoblivious routing algorithmen_US
dc.subject1-bit memory local routing algorithmen_US
dc.subjectpredecessor-oblivious routingen_US
dc.subjectorigin-oblivious routingen_US
dc.titleLocal geometric routing algorithms for edge-augmented planar graphsen_US
dc.typemaster thesisen_US
Files
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
wahid_mohammad_abdul.pdf
Size:
12.22 MB
Format:
Adobe Portable Document Format
Description:
Download
License bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
license.txt
Size:
2.25 KB
Format:
Item-specific license agreed to upon submission
Description:
Download
Collections
FGS - Electronic Theses and Practica