World Scientific
  • Search
Skip main navigation

Cookies Notification

We use cookies on this site to enhance your user experience. By continuing to browse the site, you consent to the use of our cookies. Learn More
×
Our website is made possible by displaying certain online content using javascript.
In order to view the full content, please disable your ad blocker or whitelist our website www.worldscientific.com.

System Upgrade on Tue, Oct 25th, 2022 at 2am (EDT)

Existing users will be able to log into the site and access content. However, E-commerce and registration of new users may not be available for up to 12 hours.
For online purchase, please visit us again. Contact us at [email protected] for any enquiries.

SHARED RISK RESOURCE GROUP COMPLEXITY AND APPROXIMABILITY ISSUES

    This article investigates complexity and approximability properties of combinatorial optimization problems yielded by the notion of Shared Risk Resource Group (SRRG). SRRG has been introduced in order to capture network survivability issues where a failure may break a whole set of resources, and has been formalized as colored graphs, where a set of resources is represented by a set of edges with same color. We consider here the analogous of classical problems such as determining paths or cuts with the minimum numbers of colors or color disjoint paths. These optimization problems are much more difficult than their counterparts in classical graph theory. In particular standard relationship such as the Max Flow - Min Cut equality do not hold any longer. In this article we identify cases where these problems are polynomial, for example when the edges of a given color form a connected subgraph, and otherwise give hardness and non approximability results for these problems.

    References

    • R.   Bhandari , Survivable networks: Algorithms for diverse routing ( Kluwer Academic , 1999 ) . Google Scholar
    • R. D. Carret al., On the red-blue set cover problem, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms (SODA) (Society for Industrial and Applied Mathematics, 2000) pp. 345–353. Google Scholar
    • R. Chang and S. Leu, Information Processing Letters 63(5), 277 (1997), DOI: 10.1016/S0020-0190(97)00127-0. Crossref, ISIGoogle Scholar
    • A. L. Chiu, J. Strand and R. Tkach, IEEE Communications Magazine 39(2), 81 (2001), DOI: 10.1109/35.900635. Google Scholar
    • P. Datta and A. K. Somani, Diverse routing for shared risk resource groups (SRRG) failures in WDM optical networks, Proceedings of IEEE BroadNets (2004) pp. 120–129, DOI: 10.1109/BROADNETS.2004.34. Google Scholar