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

DOI10.1137/S0097539796308485zbMath0940.68066OpenAlexW2075738659MaRDI QIDQ4268717

Jaap-Henk Hoepman, Harry Buhrman, 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

zbMATH Keywords

random graphsKolmogorov complexityrouting algorithmsaverage-case complexityspace complexitycompact routing tablescomputer networksincompressibility method

Mathematics Subject Classification ID

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

Related Items (2)

Average stretch analysis of compact routing schemes ⋮ Compact and localized distributed data structures

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