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

DOI10.1016/J.ORL.2007.10.008zbMATH Open1154.90334arXiv0710.3044OpenAlexW2064289893WikidataQ115568197 ScholiaQ115568197MaRDI QIDQ943799FDOQ943799

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

Publication date: 10 September 2008

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

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.

Full work available at URL: https://arxiv.org/abs/0710.3044

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

zbMATH Keywords

network designvirtual private networks

Mathematics Subject Classification ID

Communication networks in operations research (90B18)

Cites Work

• Provisioning a virtual private network: a network design problem for multicommodity flow
• Design of trees in the hose model: the balanced case
• Title not available (Why is that?)
• 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)