Skip to Main content Skip to Navigation
New interface
Conference papers

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
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 ∆.
Complete list of metadata

Cited literature [15 references]  Display  Hide  Download
Contributor : Fatima Zahra Moataz Connect in order to contact the contributor
Submitted on : Thursday, June 11, 2015 - 1:54:27 PM
Last modification on : Thursday, August 4, 2022 - 4:58:23 PM
Long-term archiving on: : Tuesday, April 25, 2017 - 6:51:37 AM


Files produced by the author(s)


  • HAL Id : hal-01162796, version 1


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⟩



Record views


Files downloads