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"”.

  1. 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 …

    wvu Repository record for FLOC-SPANNER: An O(1) time, locally self-stabilizing algorithm for geometric spanner construction in a wireless sensor network (opens in a new tab)

  2. 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 …

    ottawa-retro Repository record for The Exact Spanning Ratio of the Parallelogram Delaunay Graph (opens in a new tab)

  3. 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 …

    fu-berlin Repository record for Routing and Stabbing (opens in a new tab)

  4. 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 …

    unf Repository record for Fast-sparse-spanner: A practical algorithm for constructing low-stretch sparse geometric graphs (opens in a new tab) Download PDF for Fast-sparse-spanner: A practical algorithm for constructing low-stretch sparse geometric graphs (opens in a new tab)

  5. 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 …

    unf Repository record for Bounded-degree Plane Geometric Spanners: Connecting the Dots Between Theory and Practice (opens in a new tab) Download PDF for Bounded-degree Plane Geometric Spanners: Connecting the Dots Between Theory and Practice (opens in a new tab)