Space-efficient Routing Tables for Almost All Networks and the Incompressibility Method

DOI10.1137/S0097539796308485MaRDI QIDQ4268717zbMATH OpenOpenAlexFDO

Authors Harry Buhrman, Jaap-Henk Hoepman, Paul M. B. Vitányi

Publication date 28 October 1999

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/s0097539796308485, https://ir.cwi.nl/pub/1233

zbMATH Keywords

average-case complexitycompact routing tablescomputer networksincompressibility methodKolmogorov complexityrandom graphsrouting algorithmsspace complexity

Mathematics Subject Classification ID

Network design and communication in computer systems (68M10) Analysis of algorithms and problem complexity (68Q25) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Graph theory (including graph drawing) in computer science (68R10) Communication networks in operations research (90B18)

Recommendations

• A trade-off between space and efficiency for routing tables
• Universal routing schemes
• Space-efficiency for routing schemes of stretch factor three
• Lower bounds for compact routing (extended abstract)
• scientific article; zbMATH DE number 3940741

Cited in

(9)

• Compressing two-dimensional routing tables
• On the complexity of compressing two dimensional routing tables with order
• Searching among intervals and compact routing tables
• Compressing two-dimensional routing tables with order
• Compact and localized distributed data structures
• The Space Requirement of Local Forwarding on Acyclic Networks
• Space-efficiency for routing schemes of stretch factor three
• Close to linear space routing schemes
• Average stretch analysis of compact routing schemes

This page was built for publication: Space-efficient Routing Tables for Almost All Networks and the Incompressibility Method

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4268717)