Loading...
Please wait, while we are loading the content...
Similar Documents
Lower Bounds for Compact Routing (Extended Abstract) (1995)
| Content Provider | CiteSeerX |
|---|---|
| Author | Kranakis, Evangelos Krizanc, Danny |
| Description | In this paper we present lower bounds for compact routing schemes. We give (1) networks on n vertices which for any interval routing scheme,\Omega\Gamma n) routers of the network require\Omega\Gamma n) intervals on some out-going link and (2) for each d 3, networks of maximal degree d which for any interval routing scheme,\Omega\Gamma n) routers each require \Omega\Gamma n= log n) intervals on some out-going link. Our results give the best known worst-case lower bounds for interval routing. For the case of universal routing schemes we give (3) networks on n vertices which for any near optimal routing scheme with stretch factor ! 2 a total of \Omega\Gamma n 2 ) memory bits are required, and (4) for each d 3, networks of maximal degree d for which any optimal (resp., near optimal) routing scheme (resp., with stretch factor ! 2) requires a total of \Omega\Gamma n 2 = log n) (resp. \Omega\Gamma n 2 = log 2 n)) memory bits. 1980 Mathematics Subject Classification: 68Q99 C... In 17th International Symposium on Theoretical Aspects of Computer Science |
| File Format | |
| Language | English |
| Publisher | Springer |
| Publisher Date | 1995-01-01 |
| Access Restriction | Open |
| Subject Keyword | Memory Bit Maximal Degree Extended Abstract Out-going Link Interval Routing Interval Routing Scheme Omega Gamma Compact Routing Mathematics Subject Classification Stretch Factor |
| Content Type | Text |
| Resource Type | Article |
