Complexity and approximability issues of Shared Risk Resource Group

David Coudert 1 Pallab Datta 1 Stéphane Pérennes 1 Hervé Rivano 1 Marie-Emilie Voge 1
1 MASCOTTE - Algorithms, simulation, combinatorics and optimization for telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
Abstract : This article investigates the consequences of the Shared Risk Ressource Groups (SRRG) model on classical combinatorial concepts of network survivability. It focuses on complexity and approximability issues, and on the evolutions of the relationships among these questions. We introduce a combinatorial model for SRRG based on edge-colored graphs. The notions of colored cut and colored spanning tree are introduced, the hardness and non-approximability of path, cut and spanning tree colored optimization problems are proved. We provide approximation algorithms, and investigate specific polynomial cases. Deep differences between colored combinatorial questions and their counterparts in classical graph theory are shown. In particular, results concerning the relationships among colored problems are presented.
Type de document :
Rapport
[Research Report] RR-5859, INRIA. 2006, pp.20
Liste complète des métadonnées

Littérature citée [19 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00070167
Contributeur : Rapport de Recherche Inria <>
Soumis le : vendredi 19 mai 2006 - 19:18:46
Dernière modification le : samedi 17 septembre 2016 - 01:36:00
Document(s) archivé(s) le : dimanche 4 avril 2010 - 20:22:29

Fichiers

Identifiants

  • HAL Id : inria-00070167, version 1

Collections

Citation

David Coudert, Pallab Datta, Stéphane Pérennes, Hervé Rivano, Marie-Emilie Voge. Complexity and approximability issues of Shared Risk Resource Group. [Research Report] RR-5859, INRIA. 2006, pp.20. 〈inria-00070167〉

Partager

Métriques

Consultations de
la notice

376

Téléchargements du document

138