Network Reconfiguration using Cops-and-Robber GamesReportar como inadecuado

Network Reconfiguration using Cops-and-Robber Games - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

* Corresponding author 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.

Autor: David Coudert - Dorian Mazauric -



Documentos relacionados