Zurück zu den Preprints des Jahres 2007


2007-34

A Short Proof of the VPN Tree Routing Conjecture on Ring Networks

by Grandoni, F., Kaibel, V., Oriolo, V., Skutella, M..


Series: 2007-34, Preprints

MSC:
90C27 Combinatorial optimization

Abstract:
The VPN Tree Routing Conjecture states that there always exists an optimal solution to the symmetric Virtual Private Network Design (sVPND) problem where the paths between all terminals form a tree. Only recently, Hurkens, Keijsper, and Stougie gave a proof of this conjecture for the special case of ring networks. Their proof is based on a dual pair of linear programs and is somewhat in- volved. We present a short proof of a slightly stronger conjecture which might also turn out to be useful for proving the VPN Tree Routing Conjecture for general networks.

Keywords:
telecommunication networks, virtual private networks, routing