Virtual private network design : a proof of the tree routing conjecture on ring networks

Research output: Contribution to journalArticleAcademicpeer-review

20 Citations (Scopus)
116 Downloads (Pure)

Abstract

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 the VPN must be created, is a circuit. This seems to be an important step towards answering 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, in particular when the network is a tree of rings.
Original languageEnglish
Pages (from-to)482-503
JournalSIAM Journal on Discrete Mathematics
Volume21
Issue number2
DOIs
Publication statusPublished - 2007

Fingerprint Dive into the research topics of 'Virtual private network design : a proof of the tree routing conjecture on ring networks'. Together they form a unique fingerprint.

Cite this