# Distributed computing of efficient routing schemes in generalized chordal graphs

1 MASCOTTE - Algorithms, simulation, combinatorics and optimization for telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , Laboratoire I3S - COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
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$.
Keywords :
Document type :
Journal articles
Domain :

Cited literature [21 references]

https://hal.inria.fr/hal-00741970
Contributor : Nicolas Nisse <>
Submitted on : Monday, October 15, 2012 - 3:48:27 PM
Last modification on : Friday, April 12, 2019 - 10:18:03 AM
Long-term archiving on : Thursday, January 17, 2013 - 11:25:19 AM

### File

SiroccoTCSFinal.pdf
Files produced by the author(s)

### Identifiers

• HAL Id : hal-00741970, version 1

### Citation

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

Record views