Average stretch analysis of compact routing schemes

DOI10.1016/j.dam.2006.09.010zbMath1161.68362OpenAlexW2015704876MaRDI QIDQ875595

Tamar Eilam, Cyril Gavoille, David Peleg

Publication date: 13 April 2007

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2006.09.010

zbMATH Keywords

stretch factoraverage stretchcompact routing schemesinterval routing schemespivot interval routing

Mathematics Subject Classification ID

Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Designing networks with compact routing tables
• On the ratio of optimal integral and fractional covers
• Multidimensional interval routing schemes
• A survey on interval routing
• The Compactness of Interval Routing for Almost All Graphs
• Memory requirement for routing in distributed networks
• Improved routing strategies with succinct tables
• Labelling and Implicit Routing in Networks
• Routing with Polynomial Communication-Space Trade-Off
• Worst Case Bounds for Shortest Path Interval Routing
• Space-efficient Routing Tables for Almost All Networks and the Incompressibility Method
• The Compactness of Interval Routing
• A trade-off between space and efficiency for routing tables
• Compact routing schemes with low stretch factor
• Memory requirement for universal routing schemes
• Space-efficiency for routing schemes of stretch factor three

This page was built for publication: Average stretch analysis of compact routing schemes