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.

Letzte Änderung: 01.03.2018 - Ansprechpartner: Webmaster