On paths in grids with forbidden transitionsReportar como inadecuado




On paths in grids with forbidden transitions - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

1 LIMOS - Laboratoire d-Informatique, de Modélisation et d-optimisation des Systèmes 2 COATI - Combinatorics, Optimization and Algorithms for Telecommunications CRISAM - Inria Sophia Antipolis - Méditerranée , COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués

Résumé : Une transition dans un graphe est une paire d-arêtes incidentes à un même sommet. Etant donnés un graphe G = V, E, deux sommets s,t ∈ V et un ensemble associé de transitions interdites F ⊆ E × E, le problème de chemin évitant des transitions interdites consiste à décider s-il existe un chemin élémentaire de s à t qui n-utilise aucune des transitions de F. C-est-à-dire qu-il est interdit d-emprunter consécutivement deux arêtes qui soient une paire de F. Ce problème est motivé par le routage dans les réseaux routiers où une transition interdite représente une interdiction de tourner ainsi que dans les réseaux optiques avec des noeuds asymétriques. Nous prouvons que le problème est NP-difficile dans les graphes planaires et plus particulièrement dans les grilles. Nous montrons également que leproblème peut être résolu en temps polynomial dans la classe des graphes de largeur arborescente bornée.

Mots-clés : Forbidden transitions planar graph grid asymmetric nodes





Autor: Mamadou Moustapha Kanté - Fatima Zahra Moataz - Benjamin Momège - Nicolas Nisse -

Fuente: https://hal.archives-ouvertes.fr/



DESCARGAR PDF




Documentos relacionados