On compact and efficient routing in certain graph classes
- 作者：Feodor F. Dragan ; Irina Lomonosov
- 关键词：Message routing ; Localized distributed algorithms ; Tree-decomposition ; Acyclic clustering ; Chordal bipartite graphs ; Homogeneously orderable graphs
- 刊名：Discrete Applied Mathematics
- 出版年：2007
- 期刊代码：46_0166218x
- 类别：cp
- 出版时间：1 June 2007
- 卷：155
- 期：11
- 页码：1458-1470
- 文件大小：253 K
摘要
In this paper we refine the notion of tree-decomposition by introducing acyclic me="mml6">black" href="/science?_ob=MathURL&_method=retrieve&_udi=B6TYW-4NB999M-1&_mathId=mml6&_user=10&_cdi=5629&_rdoc=13&_acct=C000050221&_version=1&_userid=10&md5=7972422930cae489e4d8b46a55177fd0" title="Click to view the MathML source">(R,D)-clustering, where clusters are subsets of vertices of a graph and R and D are the maximum radius and the maximum diameter of these subsets. We design a routing scheme for graphs admitting induced acyclic me="mml7">black" href="/science?_ob=MathURL&_method=retrieve&_udi=B6TYW-4NB999M-1&_mathId=mml7&_user=10&_cdi=5629&_rdoc=13&_acct=C000050221&_version=1&_userid=10&md5=cfc9fd532a628196022eecb988c56f3c" title="Click to view the MathML source">(R,D)-clustering where the induced radius and the induced diameter of each cluster are at most 2. We show that, by constructing a family of special spanning trees, one can achieve a routing scheme of deviation me="mml8">black" href="/science?_ob=MathURL&_method=retrieve&_udi=B6TYW-4NB999M-1&_mathId=mml8&_user=10&_cdi=5629&_rdoc=13&_acct=C000050221&_version=1&_userid=10&md5=7ce7d19388104e789ea87afa4af9a8c7" title="Click to view the MathML source">Δ2R with labels of size me="mml9"> bits per vertex and me="mml10">black" href="/science?_ob=MathURL&_method=retrieve&_udi=B6TYW-4NB999M-1&_mathId=mml10&_user=10&_cdi=5629&_rdoc=13&_acct=C000050221&_version=1&_userid=10&md5=384785b41803c7dba1d45016089415b9" title="Click to view the MathML source">O(1) routing protocol for these graphs. We investigate also some special graph classes admitting induced acyclic me="mml11">black" href="/science?_ob=MathURL&_method=retrieve&_udi=B6TYW-4NB999M-1&_mathId=mml11&_user=10&_cdi=5629&_rdoc=13&_acct=C000050221&_version=1&_userid=10&md5=07a15c1eafd8c58882dd484ad33d6bad" title="Click to view the MathML source">(R,D)-clustering with induced radius and diameter less than or equal to 2, namely, chordal bipartite, homogeneously orderable, and interval graphs. We achieve the deviation me="mml12">black" href="/science?_ob=MathURL&_method=retrieve&_udi=B6TYW-4NB999M-1&_mathId=mml12&_user=10&_cdi=5629&_rdoc=13&_acct=C000050221&_version=1&_userid=10&md5=d303febae5499a721b7a546f2f26cac5" title="Click to view the MathML source">Δ=1 for interval graphs and me="mml13">black" href="/science?_ob=MathURL&_method=retrieve&_udi=B6TYW-4NB999M-1&_mathId=mml13&_user=10&_cdi=5629&_rdoc=13&_acct=C000050221&_version=1&_userid=10&md5=3e9c2f3f3a7995b75e70bbb8a7ac56a6" title="Click to view the MathML source">Δ=2 for chordal bipartite and homogeneously orderable graphs.