Distributed computing of efficient routing schemes in generalized chordal graphs - Archive ouverte HAL Access content directly
Journal Articles Theoretical Computer Science Year : 2012

Distributed computing of efficient routing schemes in generalized chordal graphs

(1) , (2, 3) , (4)
1
2
3
4
Nicolas Nisse
Ivan Rapaport
• Function : Author
• PersonId : 867484
Karol Suchan
• Function : Author
• PersonId : 905213

Abstract

Efficient algorithms for computing routing tables should take advantage of the particular properties arising in large scale networks. Two of them are of particular 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 $k$-chordal graphs, i.e., graphs with no induced cycles of length more than $k$. In the class of $k$-chordal graphs, our routing scheme achieves an additive stretch of at most $k-1$, i.e., for all pairs of nodes, the length of the route never exceeds their distance plus $k-1$. In order to compute the routing tables of any $n$-node graph with diameter $D$ we propose a distributed algorithm which uses messages of size $O(\log n)$ and takes $O(D)$ time. The corresponding routing scheme achieves the stretch of $k-1$ on $k$-chordal graphs. We then propose a routing scheme that achieves a better additive stretch of $1$ in chordal graphs (notice that chordal graphs are 3-chordal graphs). In this case, the distributed computation of the routing tables takes $O(\min\{\Delta D , n\})$ time, where $\Delta$ is the maximum degree of the graph. Our routing schemes use addresses of size $\log n$ bits and local memory of size $2(d-1) \log n$ bits per node of degree $d$.

Dates and versions

hal-00741970 , version 1 (15-10-2012)

Identifiers

• HAL Id : hal-00741970 , version 1

Cite

Nicolas Nisse, Ivan Rapaport, Karol Suchan. Distributed computing of efficient routing schemes in generalized chordal graphs. Theoretical Computer Science, 2012, 444 (27), pp.17-27. ⟨hal-00741970⟩

282 View