We consider the following network design problem, that we call the Generalized Terminal Backup Problem: given a graph (or a hypergraph) $G_0=(V, {E}_0)$, a set of (at least 2) terminals $T\subseteq V$ and a requirement $r(t)$ for every $t\in T$, find a multigraph $G=(V,E)$ such that $\lambda_{G_0+G}(t, T-t)\ge r(t)$ for any $t\in T$. In the minimum cost version the objective is to find $G$ minimizing the total cost $c(E)=\sum_{uv\in E}c(uv)$, given also costs $c(uv)\ge 0$ for every pair $u,v\in V$. In the degree-specified version the question is to decide whether such a $G$ exists, satisfying that the number of edges is a prescribed value $m(v)$ at each node $v\in V$. The Terminal Backup Problem solved in [1] is the special case where $G_0$ is the empty graph and $r(t)=1$ for every terminal $t\in T$. We solve the Generalized Terminal Backup Problem in the following two cases.
Previous version can be found here.
Bibtex entry:
@techreport{egres-13-07,
AUTHOR | = | {Bern{\'a}th, Attila and Kobayashi, Yusuke and Matsuoka, Tatsuya}, |
TITLE | = | {The Generalized Terminal Backup Problem}, |
NOTE | = | {{\tt www.cs.elte.hu/egres}}, |
INSTITUTION | = | {Egerv{\'a}ry Research Group, Budapest}, |
YEAR | = | {2013}, |
NUMBER | = | {TR-2013-07} |