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


https://hal.inria.fr/hal-00741970
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

Fichier

SiroccoTCSFinal.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00741970, version 1

Collections

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>

Partager

Métriques

Consultations de
la notice

227

Téléchargements du document

96