2007/10/16 by Fabrizio Grandoni, Grandoni, Fabrizio, Volker Kaibel +5
Mathematics · #68R10 #90B18 #90C27 #Combinatorics (math.CO) #FOS: Mathematics #Optimization and Control (math.OC) #math.CO #math.OC #msc:68R10 #msc:90B18 #msc:90C27
paper · pdf · doi:10.48550/arxiv.0710.3044
Accepted for publication in Oper. Res. Lett.; referee's comments incorporated
arxiv created 2007/10/26 · arxiv updated 2011/11/09
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.