Global ETD Search
Search theses and dissertations gathered from participating repositories worldwide. Every result links back to the library that holds it. No account is needed.
Results
Showing 1 to 6 of 6 for “"geometric spanner"”.
-
FLOC-SPANNER: An O(1) time, locally self-stabilizing algorithm for geometric spanner construction in a wireless sensor network
Geometric spanners are a popular form of topology control in wireless networks because they yield an efficient, reduced interference subgraph for both unicast and broadcast routing.;In this thesis work a distributed algorithm for creation of geometric spanners in a wireless sensor network is …
-
The Exact Spanning Ratio of the Parallelogram Delaunay Graph
Finding the exact spanning ratio of a Delaunay graph has been one of the longstanding open problems in Computational Geometry. Currently there are only four convex shapes for which the exact spanning ratio of their Delaunay graph is known: the equilateral triangle, the square, the regular hexagon …
-
Routing and Stabbing
ROUTING. Let G be a simple, connected, undirected graph. We consider routing with preprocessing in G. In a preprocessing step, each vertex of G receives a label and a routing table. Then, we must be able to route a packet between any two vertices s and t of G, where each step may use only the label …
-
Fast-sparse-spanner: A practical algorithm for constructing low-stretch sparse geometric graphs
When constructing geometric graphs (vertices are points and edges are line segments connecting point pairs) on pointsets, stretch-factor (worst-case detour between any point pair) is often considered a quality metric. A low stretch-factor (a quantity that is usually > 1) guarantees short paths …
-
Bounded-degree Plane Geometric Spanners: Connecting the Dots Between Theory and Practice
The construction of bounded-degree plane geometric spanners has been a focus of interest since 2002 when Bose, Gudmundsson, and Smid proposed the first algorithm to construct such spanners. To date, eleven algorithms have been designed with various trade-offs in degree and stretch factor. We have …