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 <>
Submitted on : Friday, May 19, 2006 - 8:08:05 PM
Last modification on : Monday, October 12, 2020 - 10:30:21 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