by Grandoni, F., Kaibel, V., Oriolo, V., Skutella, M..
Series: 2007-34, Preprints
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