Finding Paths in Grids with Forbidden Transitions

Abstract : A transition in a graph is a pair of adjacent edges. Given a graph G = (V, E), a set of forbidden transitions F ⊆ E × E and two vertices s, t ∈ V , we study the problem of finding a path from s to t which uses none of the forbidden transitions of F. This means that it is forbidden for the path to consecutively use two edges forming a pair in F. The study of this problem is motivated by routing in road networks in which forbidden transitions are associated to prohibited turns as well as routing in optical networks with asymmetric nodes, which are nodes where a signal on an ingress port can only reach a subset of egress ports. If the path is not required to be elementary, the problem can be solved in polynomial time. On the other side, if the path has to be elementary, the problem is known to be NP-complete in general graphs [Szeider 2003]. In this paper, we study the problem of finding an elementary path avoiding forbidden transitions in planar graphs. We prove that the problem is NP-complete in planar graphs and particularly in grids. In addition, we show that the problem can be solved in polynomial time in graphs with bounded treewidth. More precisely, we show that there is an algorithm which solves the problem in time O((3∆(k + 1)) 2k+4 n)) in n-node graphs with treewidth at most k and maximum degree ∆.
Type de document :
Communication dans un congrès
WG 2015, 41st International Workshop on Graph-Theoretic Concepts in Computer Science, Jun 2015, Munich, Germany
Liste complète des métadonnées

https://hal.inria.fr/hal-01162796
Contributeur : Fatima Zahra Moataz <>
Soumis le : jeudi 11 juin 2015 - 13:54:27
Dernière modification le : mercredi 14 décembre 2016 - 01:03:35

Fichier

PAFT_WGV0.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01162796, version 1

Citation

Mamadou Moustapha Kanté, Fatima Zahra Moataz, Benjamin Momège, Nicolas Nisse. Finding Paths in Grids with Forbidden Transitions. WG 2015, 41st International Workshop on Graph-Theoretic Concepts in Computer Science, Jun 2015, Munich, Germany. <hal-01162796>

Partager

Métriques

Consultations de
la notice

479

Téléchargements du document

88