Finding Paths in Grids with Forbidden Transitions

Mamadou Moustapha Kanté 1 Fatima Zahra Moataz 2 Benjamin Momège 2 Nicolas Nisse 2
2 COATI - Combinatorics, Optimization and Algorithms for Telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , Laboratoire I3S - COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
Résumé : Une transition dans un graphe est une paire d'arêtes incidente a 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 le problème peut être résolu en temps polynomial dans la classe des graphes de largeur arborescente bornée.
Complete list of metadatas

Cited literature [14 references]  Display  Hide  Download

https://hal.inria.fr/hal-01115395
Contributor : Fatima Zahra Moataz <>
Submitted on : Wednesday, February 11, 2015 - 10:10:24 AM
Last modification on : Friday, March 29, 2019 - 3:20:02 PM
Long-term archiving on : Thursday, May 28, 2015 - 9:50:22 AM

File

PAFT.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01115395, version 1

Citation

Mamadou Moustapha Kanté, Fatima Zahra Moataz, Benjamin Momège, Nicolas Nisse. Finding Paths in Grids with Forbidden Transitions. [Research Report] Inria Sophia Antipolis; Univeristé Nice Sophia Antipolis; CNRS. 2015. ⟨hal-01115395⟩

Share

Metrics

Record views

560

Files downloads

631