Abstract
An \emph{$(n,k,r)$-network} is a triple $N=(G,\inp,\outp)$ where $G=(V,E)$is a graph and $\inp,\outp$ are non-negative integer functions defined on $V$ calledthe \emph{input} and \emph{output} functions, such that for any $v \in V$,$\inp(v)+\outp(v)+ \degree(v)\leq 2r$ where $\degree(v)$ is the degree of $v$ in thegraph $G$. The total number of inputs is $\inp(V)=\sum_{v\in V}\inp(v)=n$, and the total number of outputs is $\outp(V)=\sum_{v\in V}\outp(v)=n+k$.An $(n,k,r)$-network is \emph{valid}, if for any \emph{faulty} outputfunction $\outp'$ (that is such that $0\leq \outp'(v) \leq \outp(v)$ for any $v\in V$, and $\outp'(V) = n$), there are $n$ edge-disjoint paths in $G$such that each vertex $v\in V$ is the initial vertex of $\inp(v)$ pathsand the terminal vertex of $\outp'(v)$ paths.We investigate the design problem of determining the minimum number ${\cal N}(n,k,r)$ ofvertices in a valid $(n,k,r)$-network and of constructing minimum$(n,k,r)$-networks, or at least valid $(n,k,r)$-networks with a numberof vertices close to the optimal value.We first give some upper bounds on ${\cal N}(n,k,r)$.We show ${\cal N}(n,k,r)\leq \left\lceil \frac{k+2}{2r-2}\right\rceil \left\lceil\frac{n}{2}\right\rceil$. When $r\geq k/2$, we prove a better upper bound: ${\cal N}(n,k,r) \leq \frac{r-2+k/2}{r^2-2r+k/2} n + O(1)$.Next, we establish some lower bounds. We show that if $k\geq r$, then${\cal N}(n,k,r) \geq \frac{3n+k}{2r}$. We improve this bound when $k\geq 2r$:$\displaystyle {\cal N}(n,k,r) \geq \formule$.Finally, we determine ${\cal N}(n,k,r)$ up to additive constants for $k\leq 6$.