HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation

Repartitors, selectors and superselectors

Frédéric Havet 1
1 MASCOTTE - Algorithms, simulation, combinatorics and optimization for telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , Laboratoire I3S - COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
Abstract : 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
Document type :
Complete list of metadata

Cited literature [10 references]  Display  Hide  Download

Contributor : Rapport de Recherche Inria Connect in order to contact the contributor
Submitted on : Friday, May 19, 2006 - 8:08:05 PM
Last modification on : Friday, February 4, 2022 - 3:11:27 AM
Long-term archiving on: : Sunday, April 4, 2010 - 8:57:22 PM


  • HAL Id : inria-00070327, version 1



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



Record views


Files downloads