Network Reconfiguration using Cops-and-Robber Games

David Coudert 1, * Dorian Mazauric 1
* Auteur correspondant
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 : The process number is the number of requests that have to be simultaneously disturbed during a routing reconfiguration phase of a connection oriented network. From a graph theory point of view, it is similar to the pathwidth. However they are not always equal in general graphs. Determining these parameters is in general NP-complete. In this paper, we propose a polynomial algorithm to compute an approximation of the process number of digraphs, improving the efficiency of the previous exponential algorithm.
Type de document :
Rapport
[Research Report] RR-6694, INRIA. 2008


https://hal.inria.fr/inria-00315568
Contributeur : David Coudert <>
Soumis le : jeudi 16 octobre 2008 - 17:47:13
Dernière modification le : vendredi 16 septembre 2016 - 15:21:16

Fichier

RR-6694.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00315568, version 3

Collections

Citation

David Coudert, Dorian Mazauric. Network Reconfiguration using Cops-and-Robber Games. [Research Report] RR-6694, INRIA. 2008. <inria-00315568v3>

Exporter

Partager

Métriques

Consultations de
la notice

195

Téléchargements du document

77