2005
Virtual private network design: a proof of the tree routing conjecture on ring networks
Publication
Publication
Presented at the
International Conference on Integer Programming and Combinatorial Optimization
A basic question in Virtual Private Network (VPN) design is if the symmetric version of
the problem always has an optimal solution which is a tree network. An affirmative answer
would imply that the symmetric VPN problem is solvable in polynomial time. We give an
affirmative answer in case the communication network within which to create the VPN is a
circuit. This seems to be an important step towards an answer to the general question. The
proof relies on a dual pair of linear programs and actually implies an even stronger property
of VPNs. We show that this property also holds for some other special cases of the problem.
| Additional Metadata | |
|---|---|
| Springer | |
| Lecture Notes in Computer Science | |
| International Conference on Integer Programming and Combinatorial Optimization | |
| Organisation | Networks and Optimization |
|
Hurkens, C., Keijsper, J. C. M., & Stougie, L. (2005). Virtual private network design: a proof of the tree routing conjecture on ring networks. In Proceedings of the 11th International Conference on Integer Programming and Combinatorial Optimization (pp. 407–421). Springer. |
|