• Refine Query
  • Source
  • Publication year
  • to
  • Language
  • 1
  • Tagged with
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • About
  • The Global ETD Search service is a free service for researchers to find electronic theses and dissertations. This service is provided by the Networked Digital Library of Theses and Dissertations.
    Our metadata is collected from universities around the world. If you manage a university/consortium/country archive and want to be added, details can be found on the NDLTD website.
1

Local Routing in Spanners Based on WSPDs

Paradis, Frédérik January 2017 (has links)
The well-separated pair decomposition (WSPD) of the complete Euclidean graph defined on points in R 2 , introduced by Callahan and Kosaraju [JACM, 42 (1): 67-90, 1995], is a technique for partitioning the edges of the complete graph based on length into a linear number of sets. Among the many different applications of WSPDs, Callahan and Kosaraju proved that the sparse subgraph that results by selecting an arbitrary edge from each set (called WSPD-spanner) is a 1 + 8/(s − 4)-spanner, where s > 4 is the separation ratio used for partitioning the edges. Although competitive local-routing strategies exist for various spanners such as Yao-graphs, Θ-graphs, and variants of Delaunay graphs, few local-routing strategies are known for any WSPD-spanner. Our main contribution is a local-routing algorithm with a near-optimal competitive routing ratio of 1 + O(1/s) on a WSPD-spanner. Specifically, using Callahan and Kosaraju’s fair split-tree, we show how to build a WSPD-spanner with spanning ratio 1 + 4/s + 4/(s − 2) which is a slight improvement over 1 + 8/(s − 4). We then present a 2-local and a 1-local routing algorithm on this spanner with competitive routing ratios of 1 + 6/(s − 2) + 4/s and 1 + 8/(s − 2) + 4/s + 8/s 2 , respectively. Moreover, we prove that there exists a point set for which our WSPD-spanner has a spanning ratio of at least 1 + 8/s, thereby proving the near-optimality of its spanning ratio and the near-optimality of the routing ratio of both our routing algorithms.

Page generated in 0.1203 seconds