Compute Canada

View All Papers
To Submit a new publication, Please visit the User's Section (logged in users only)

Publications:
To view a publication's Abstract (if available), click on publication's title
Author(s)
     Paz Carmi, Mathieu Couture, Michiel Smid, Daming Xu, Prosenjit Bose
Title
     On a family of strong geometric spanners that admit local routing strategies
Publication Name
     10th International Workshop on Algorithms and Data Structures (WADS) 		Publication Type
     
Publisher
     Springer 		Place
      Halifax, Canada
Editor(s)
     
Number
      		School
      Scool of Computer Science, Carleton University
Volume
      		Chapter
      		Pages
     
Other Publication Information
      		Publication Year
     2007
Abstract
     We introduce a family of directed geometric graphs, denoted G(lambda,theta), that depend on two parameters lambda and theta. For 0 <= theta < pi/2 and 1/2 < lambda < 1, the G(lambda,theta) graph is a strong t-spanner, with t=1/((1-lambda)cos(theta)). The out-degree of a node in the G(lambda,theta) graph is at most floor(2pi/(min(theta, arccos(1/2lambda))). Moreover, we show that routing can be achieved locally on G(lambda,theta). Next, we show that all strong t-spanners are also t-spanners of the unit disk graph. Simulations for various values of the parameters lambda and theta indicate that for random point sets, the spanning ratio of G(lambda,theta) is better than the proven theoretical bounds.
Keywords
     
Website
     http://cg.scs.carleton.ca/~mathieu/publications.html
Paper Status
     Accepted 		DOI / Publication ID
     



View All Papers