Distributed computing of efficient routing schemes in generalized chordal graphs

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$.
Type de document :
Article dans une revue
Theoretical Computer Science, Elsevier, 2012, 444 (27), pp.17-27
Liste complète des métadonnées

Littérature citée [21 références]  Voir  Masquer  Télécharger

Contributeur : Nicolas Nisse <>
Soumis le : lundi 15 octobre 2012 - 15:48:27
Dernière modification le : mardi 16 octobre 2012 - 08:41:21
Document(s) archivé(s) le : jeudi 17 janvier 2013 - 11:25:19


Fichiers produits par l'(les) auteur(s)


  • HAL Id : hal-00741970, version 1



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〉



Consultations de
la notice


Téléchargements du document