Springe direkt zu Inhalt

Nils Goldmann:

Complexity Analysis for a Labeled Routing Scheme


Let us consider eps in (0,1)  and an undirected, weighted graph G with n nodes and low doubling dimension d. Konjevod, Richa and Xia introduced a (1 + eps)-stretch labeled routing scheme with (log n)-bit routing labels, O(log^2 n / log log n)-bit packet headers and ((1/eps)^O(d) log^3 n)-bit routing tables at every node for such graphs G. Now, we want to analyze the preprocessing step of this method. We show that the running time for this is O(n^3 + eps^{-1} n^2 log^2 n).

Also, we adapt the method for Unit Disk Graphs and improve the running time to be O(eps^{-1} n^2 log^2 n). We show that the doubling dimension for Unit Disk Graphs is O(max(1, D^2), with D being the diameter of the graph. Additionally, we simplfy Konjevod et al.'s routing algorithm and transform it into a recursive form.

Bachelor of Science (B.Sc.)