BEGIN:VCALENDAR
PRODID:-//Mercury//HGEvent//EN
VERSION:2.0
METHOD:PUBLISH
BEGIN:VEVENT
STATUS:CONFIRMED
LAST-MODIFIED:20120912T122329
PRIORITY:0
CLASS:PUBLIC
UID:ATEvent-eed436ece7e23bbcfe0d4623c4969225
SUMMARY:Prosenjit Bose\, Carleton University\, Canada
DESCRIPTION:Title: Competitive Routing on a Variant of the Delaunay Triangulation\nAbstract: A subgraph H of a weighted graph G is a t-spanner of G provided that for every edge xy in G\, the weight of the shortest path between x and y in H is at most t times the weight of xy. It is known that the Delaunay triangulation of a point set P (where the empty region is an equilateral triangle) is a 2-spanner of the complete Euclidean graph. We present a new and simple proof of this spanning ratio that allows us to route competitively on this graph. Specifically\, we present a deterministic local routing scheme that is guaranteed to find a short path between any pair of vertices in this Delaunay triangulation. We guarantee that the length of the path is at most 5/sqrt(3) times the Euclidean distance between the pair of vertices. Moreover\, we show that no local routing scheme can achieve a better competitive spanning ratio thereby implying that our routing scheme is optimal. This is somewhat surprising since the spanning ratio is 2.\n
DTSTART:20120405T133000
DTEND:20120405T133000
CREATED:20120912T122329
DTSTAMP:20120912T122329
SEQUENCE:0
LOCATION:
END:VEVENT
END:VCALENDAR