Paper Info
Title
A Lower Bound for Oblivious Dimensional Routing
Abstract
In this work we consider deterministic oblivious dimensional routing algorithms on d -dimensional meshes. In oblivious dimensional routing algorithms the path of a packet depends only on the source and destination node of the packet. Furthermore packets use a shortest path with a minimal number of bends. We present an ***(kn (d + 1)/2) step lower bound for oblivious dimensional k -k routing algorithms on d -dimensional meshes for odd d 1 and show that the bound is tight.
Year
DOI
Venue
2009
10.1007/978-3-642-03869-3_92
Euro-Par
Keywords
Field
DocType
oblivious dimensional routing,lower bound,shortest path,dimensional mesh,deterministic oblivious dimensional,destination node,minimal number,oblivious dimensional k
Polygon mesh,Shortest path problem,Upper and lower bounds,Computer science,Network packet,Directed graph,Destination-Sequenced Distance Vector routing,Distributed computing,Routing algorithm
Conference
Volume
ISSN
Citations 
5704
0302-9743
2
PageRank 
References 
Authors
0.43
15
1
Name
Order
Citations
PageRank
Andre Osterloh1104.49