Repartitors, selectors and superselectors - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 2005

Repartitors, selectors and superselectors

Résumé

An $(n,p,n+f)$-network $G$ is a graph $(V,E)$ where the vertex set $V$ is partitioned into four subsets $\calP$, $\calI$, $\calO$ and $\calS$ called respectively the priorities, the ordinary inputs, the outputs and the switches, satisfying the following constraints: there are $p$ priorities, $n-p$ ordinary inputs and $n+f$ outputs; each priority, each ordinary input and each output is connected to exactly one switch; switches have degree at most 4. An $(n,p,n+f)$-network is a $(n,p,f)$-repartitor if for any disjoint subsets $\calF$ and $\calB$ of $\calO$ with $|\calF|=f$ and $|\calB|=p$, there exist in $G$, $n$ edge-disjoint paths, $p$ of them from $\calP$ to $\calB$ and the $n-p$ others joining $\calI$ to $\calO\setminus(\calB\cup\calF)$. The problem is to determine the minimum number $R(n,p,f)$ of switches of an $(n,p,f)$-repartitor and to construct a repartitor with the smallest number of switches. In this paper, we show how to build general repartitors from $(n,0,f)$-repartitors also called $(n,n+f)$-selectors. We then consrtuct selectors using more powerful networks called superselectors. An $(n,0,n)$-network is an $n$-superselector

Domaines

Autre [cs.OH]
Fichier principal
Vignette du fichier
RR-5686.pdf (266.5 Ko) Télécharger le fichier
Loading...

Dates et versions

inria-00070327 , version 1 (19-05-2006)

Identifiants

  • HAL Id : inria-00070327 , version 1

Citer

Frédéric Havet. Repartitors, selectors and superselectors. [Research Report] RR-5686, INRIA. 2005, pp.28. ⟨inria-00070327⟩
81 Consultations
163 Téléchargements

Partager

Gmail Facebook X LinkedIn More