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
Reports

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 :
Reports
Complete list of metadata

Cited literature [10 references]  Display  Hide  Download

https://hal.inria.fr/inria-00070327
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

Identifiers

  • HAL Id : inria-00070327, version 1

Collections

Citation

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

Share

Metrics

Record views

69

Files downloads

140