📖
Minimal Selectors and Fault Tolerant Networks
Omid Amini, Frédéric Giroire, Florian Huc, Stéphane Pérennes

Minimal Selectors and Fault Tolerant Networks

Science & Mathematics Published 2006 Verification Pending

Overview & Synopsis

Un reseau $\plk$ est un graphe non oriente avec $p + \lambda$ entrees, $p + k$ sorties et des noeuds internes de degre $4$. Un reseau $\plk$ est valide si pour n'importe quel choix de $p$ entrees et de $p$ sorties il existe $p$ chemins aretes disjoints reliant les entrees aux sorties. Dans le cas particulier $\lambda = 0$, un reseau $\plk$ est un {selecteur}. Notre objectif est de determiner $N\plk$ : le nombre minimum de noeuds d'un reseau $\plk$ valide. Pour cela, on utilise une condition suffisante de validite qui nous permet d'obtenir les bornes inferieures pour $N\plk$. D'autre part on propose des constructions de reseaux valides utlisant des {expandeurs}, ce qui donne les bornes supperieures. Le probleme depend tres fortement des ordres de $\lambda$ et $k$, par exemple lorsque $\lambda $ et $k$ sont petits par rapport a $p$, certains patterns sont interdits. Pour les valeurs plus grandes de $\lambda$ et $k$, on peut construire un reseau $\plk$ valide a partir d'un graphe ayant de bonne propriete d'expansion concernant les petits ensembles de sommets. Cela nous emmene a introduire un nouveau parametre : la {robustness}. On obtient dans de nombreux cas des bornes asymptotiques exactes.

Indexed from repository: HAL Open Science (hal.science)
Loading document from verified source...
Keyboard Shortcuts: ← / → for pages • + / - for zoom • 0 to fit width Powered by Mozilla PDF.js v3.11

Document Information

Document Title Minimal Selectors and Fault Tolerant Networks
Author / Organization Omid Amini, Frédéric Giroire, Florian Huc, Stéphane Pérennes
Subject & Discipline Multidisciplinary Academic Open Research
Categories Science & Mathematics
Publication Year 2006
License / Rights Open Access / Creative Commons
Resource Verification Listed PDF (Verification Pending)
Original Host Website HAL Open Science (hal.science)
File Format application/pdf (Portable Document Format)
Language EN
Catalog ID DOC-147043
Original Source Link Visit Source Page on hal.science »