TR-2015-02

A succinct tree coding for greedy navigation

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



Abstract

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:

@techreport{egres-15-02,
AUTHOR = {Kir{\'a}ly, Zolt{\'a}n and Kisfaludi-Bak, S{\'a}ndor},
TITLE = {A succinct tree coding for greedy navigation},
NOTE= {{\tt www.cs.elte.hu/egres}},
INSTITUTION = {Egerv{\'a}ry Research Group, Budapest},
YEAR = {2015},
NUMBER = {TR-2015-02}
}


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