A succinct tree coding for greedy navigation

Zoltán Király, Sándor Kisfaludi-Bak


We present a succinct tree coding that enables greedy routing in arbitrary connected graphs. The worst-case length of vertex addresses is at most $3\log n + \log \log n + 3.59$ bits for $n$ vertex graphs. We define a distance function with which greedy message forwarding is guaranteed to deliver messages between any pair of vertices in the graph.

Bibtex entry:

AUTHOR = {Kir{\'a}ly, Zolt{\'a}n and Kisfaludi-Bak, S{\'a}ndor},
TITLE = {A succinct tree coding for greedy navigation},
NOTE= {{\tt}},
INSTITUTION = {Egerv{\'a}ry Research Group, Budapest},
YEAR = {2015},
NUMBER = {TR-2015-02}

Last modification: 10.9.2021. Please email your comments to Tamás Király!