Voir la notice de l'article provenant de la source Numdam
In this paper, we propose a method which enables to construct almost optimal broadcast schemes on an -dimensional hypercube in the circuit switched, -port model. In this model, an initiator must inform all the nodes of the network in a sequence of rounds. During a round, vertices communicate along arc-disjoint dipaths. Our construction is based on particular sequences of nested binary codes having the property that each code can inform the next one in a single round. This last property is insured by a flow technique and results about symmetric flow networks. We apply the method to design optimal schemes improving and generalizing the previous results.
Dans cet article nous proposons une méthode pour construire des protocoles de diffusion quasi optimaux dans l’hypercube, ceci dans le modèle commutation de circuits et diffusion simultanée sur tous les ports. Dans ce modèle un sommet initiateur doit informer tous les autres nœuds du réseau en un minimum d’étapes. Durant une étape les communications ont lieu via des chemins arc-disjoints Notre construction utilise des séquences de codes binaires emboîtés les uns dans les autres avec la propriété que les sommets de chaque code peuvent informer ceux du code suivant en une étape. Cette dernière condition est assurée à l’aide d’outils venant de la théorie des flots en particulier des flots symétriques. Nous appliquons la méthode pour concevoir des protocoles optimaux ou quasi optimaux améliorant ainsi les résultats précédemment connus.
@article{AIF_1999__49_3_787_0,
author = {Bermond, Jean-Claude and Bonnecaze, A. and Kodate, T. and P\'erennes, St\'ephane and Sol\'e, Patrick},
title = {Symmetric flows and broadcasting in hypercubes},
journal = {Annales de l'Institut Fourier},
pages = {787--807},
publisher = {Association des Annales de l{\textquoteright}institut Fourier},
volume = {49},
number = {3},
year = {1999},
doi = {10.5802/aif.1692},
mrnumber = {2000g:90014},
zbl = {0928.68133},
language = {en},
url = {http://geodesic.mathdoc.fr/articles/10.5802/aif.1692/}
}
TY - JOUR AU - Bermond, Jean-Claude AU - Bonnecaze, A. AU - Kodate, T. AU - Pérennes, Stéphane AU - Solé, Patrick TI - Symmetric flows and broadcasting in hypercubes JO - Annales de l'Institut Fourier PY - 1999 SP - 787 EP - 807 VL - 49 IS - 3 PB - Association des Annales de l’institut Fourier UR - http://geodesic.mathdoc.fr/articles/10.5802/aif.1692/ DO - 10.5802/aif.1692 LA - en ID - AIF_1999__49_3_787_0 ER -
%0 Journal Article %A Bermond, Jean-Claude %A Bonnecaze, A. %A Kodate, T. %A Pérennes, Stéphane %A Solé, Patrick %T Symmetric flows and broadcasting in hypercubes %J Annales de l'Institut Fourier %D 1999 %P 787-807 %V 49 %N 3 %I Association des Annales de l’institut Fourier %U http://geodesic.mathdoc.fr/articles/10.5802/aif.1692/ %R 10.5802/aif.1692 %G en %F AIF_1999__49_3_787_0
Bermond, Jean-Claude; Bonnecaze, A.; Kodate, T.; Pérennes, Stéphane; Solé, Patrick. Symmetric flows and broadcasting in hypercubes. Annales de l'Institut Fourier, Tome 49 (1999) no. 3, pp. 787-807. doi: 10.5802/aif.1692
Cité par Sources :