کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
420062 | 683891 | 2007 | 13 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: On compact and efficient routing in certain graph classes On compact and efficient routing in certain graph classes](/preview/png/420062.png)
In this paper we refine the notion of tree-decomposition by introducing acyclic (R,D)(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 (R,D)(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 Δ⩽2RΔ⩽2R with labels of size O(log3n/loglogn) bits per vertex and O(1)O(1) routing protocol for these graphs. We investigate also some special graph classes admitting induced acyclic (R,D)(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 Δ=1Δ=1 for interval graphs and Δ=2Δ=2 for chordal bipartite and homogeneously orderable graphs.
Journal: Discrete Applied Mathematics - Volume 155, Issue 11, 1 June 2007, Pages 1458–1470