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(log~3 n/log log n) bits per node, and O(log~2 n/ log log n) 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.
展开▼
机译：本文涉及在弦图中使用简洁表进行路由。我们展示了如何在多项式时间内为每个n节点弦图构造一种使用路由表和每个节点O（log〜3 n / log log n）位和O（log〜2 n / log）地址的路由方案log n）位不可更改的标头，以使任意两个节点之间的路由长度最大为图中节点之间的距离加两个。
展开▼
