TITLE: Improved Compact Routing Scheme for Chordal Graphs
AUTHORS: Yon Dourisboure and Cyril Gavoille
ABSTRACT:
This paper concerns routing with succinct tables in chordal graphs. We
show how to construct in polynomial time, for every n-node
chordal graph, a routing scheme using routing tables and addresses of
O(log3n/loglogn) bits per node, and
O(log2n/loglogn) bit not alterable headers
such that the length of the route between any two nodes is at most the
distance between the nodes in the graph plus two.