Approximation algorithm for optimal location of concentrators and design of Capacitated Survivable Backbone Networks

Arun Jotshi, Sarat Puthenpura and Wenjie Zhao

International Journal of Mathematics in Operational Research, 2011, vol. 3, issue 1, 22-43

Abstract: We focus on the problem of selecting concentrator locations to minimise the access network costs. This falls under the general class of Uncapacitated Facility Location (UFL) problem. We present an approximation algorithm along with some computational results. We also study the problem of designing a Capacitated Survivable Backbone Network (CSBN) with the property that there is at least one route present between all the communicating node pairs in the case of a single link failure. Mathematical formulation to efficiently solve the survivable backbone network design problem is presented. The methodologies developed are applied to a real world setting obtaining optimal or near-optimal results.

Keywords: facility location; access networks; survivable backbone networks; capacitated backbone networks; k-connected networks; concentrator locations; network costs; link failure; network design. (search for similar items in EconPapers)
Date: 2011
References: Add references at CitEc
Citations:

Downloads: (external link)
http://www.inderscience.com/link.php?id=37311 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:ids:ijmore:v:3:y:2011:i:1:p:22-43

Access Statistics for this article

More articles in International Journal of Mathematics in Operational Research from Inderscience Enterprises Ltd
Bibliographic data for series maintained by Sarah Parker ().