Local geometric routing algorithms for edge-augmented planar graphs
Abstract
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).
Collections
Related items
Showing items related by title, author, creator and subject.
-
MICA: A Hybrid Method for Corpus-Based Algorithmic Composition of Music Based on Genetic Algorithms, Zipf's Law, and Markov Models
Nagelberg, Alan (2014-01-16)An algorithm known as the Musical Imitation and Creativity Algorithm (MICA) that composes stylistic music based on a corpus of works in a given style is presented. The corpus works are digital music scores created from the ... -
Adaptive visual representations for autonomous mobile robots using competitive learning algorithms
McNeill, Dean K. (1999-05-01)This thesis examines issues surrounding the class of unsupervised artificial neural network learning algorithms known as competitive learning. Four variations of competitive learning algorithms are presented and compared, ... -
A data analytic algorithm for managing, querying, and processing uncertain big data in cloud environments
Jiang, Fan; Leung, Carson K. (MDPI, 2015-12)Big data are everywhere as high volumes of varieties of valuable precise and uncertain data can be easily collected or generated at high velocity in various real-life applications. Embedded in these big data are rich sets ...