Distributed computing of efficient routing schemes in generalized chordal graphs

详细信息	查看全文 | 推荐本文 |

• 作者：Nicolas Nisse^a ; ^{nicolas.nisse@inria.fr} ; Ivan Rapaport^b ; Karol Suchan^c ; ^d ; ^{karol.suchan@uai.cl}
• 关键词：Routing scheme ; Stretch ; Chordal graph ; Distributed algorithm
• 刊名：Theoretical Computer Science
• 出版年：2012
• 期刊代码：114_03043975
• 类别：cp
• 出版时间：27 July, 2012
• 卷：444
• 期：Complete
• 页码：17-27
• 文件大小：309 K

摘要

Efficient algorithms for computing routing tables should take advantage of particular properties arising in large scale networks. Two of them are of special interest: low (logarithmic) diameter and high clustering coefficient.

High clustering coefficient implies the existence of few large induced cycles. Considering this fact, we propose here a routing scheme that computes short routes in the class of -chordal graphs, i.e., graphs with no induced cycles of length more than . In the class of -chordal graphs, our routing scheme achieves an additive stretch of at most , i.e., for all pairs of nodes, the length of the route never exceeds their distance plus .

In order to compute the routing tables of any -node graph with diameter we propose a distributed algorithm which uses -bit messages and takes time. The corresponding routing scheme achieves the stretch of on -chordal graphs. We then propose a routing scheme that achieves a better additive stretch of in chordal graphs (notice that chordal graphs are 3-chordal graphs). In this case, distributed computation of routing tables takes time, where is the maximum degree of the graph. Our routing schemes use addresses of size bits and local memory of size bits per node of degree .