A short proof of the VPN tree routing conjecture on ring networks

DOI10.1016/J.ORL.2007.10.008MaRDI QIDQ943799zbMATH OpenOpenAlexWikidataFDO

Authors Fabrizio Grandoni, Volker Kaibel, Gianpaolo Oriolo, Martin Skutella

Publication date 10 September 2008

Published in Operations Research Letters (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0710.3044, http://hdl.handle.net/2108/31217

zbMATH Keywords

network designvirtual private networks

Mathematics Subject Classification ID

Communication networks in operations research (90B18)

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 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.

Recommendations

• Virtual Private Network Design: A Proof of the Tree Routing Conjecture on Ring Networks
• Virtual Private Network Design: A Proof of the Tree Routing Conjecture on Ring Networks
• The VPN conjecture is true
• The VPN Problem with Concave Costs
• Virtual private network design

Cites work

• scientific article; zbMATH DE number 5485556 (Why is no real title available?)
• Design of trees in the hose model: the balanced case
• Provisioning a virtual private network: a network design problem for multicommodity flow
• Virtual Private Network Design: A Proof of the Tree Routing Conjecture on Ring Networks

Cited in

(4)

• Virtual Private Network Design: A Proof of the Tree Routing Conjecture on Ring Networks
• Virtual Private Network Design: A Proof of the Tree Routing Conjecture on Ring Networks
• Exploring the tractability of the capped hose model
• Robust network design: formulations, valid inequalities, and computations

This page was built for publication: A short proof of the VPN tree routing conjecture on ring networks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q943799)