07-34
A Short Proof of the VPN Tree Routing Conjecture on Ring Networks
by Grandoni, F., Kaibel, V.; Oriolo, V.; Skutella, M.
Preprint series: 07-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 involved. 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
The author(s) agree, that this abstract may be stored asfull text and distributed as such by abstracting services.