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

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

2007-10-16

arxiv.org/abs/0710.3044v2

Mathematics

Combinatorics

Accepted for publication in Oper. Res. Lett.; referee's comments incorporated

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

A Short Proof of the VPN Tree Routing Conjecture on Ring Networks does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with A Short Proof of the VPN Tree Routing Conjecture on Ring Networks, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A Short Proof of the VPN Tree Routing Conjecture on Ring Networks will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-714348