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 metadatas

Cited literature [15 references]  Display  Hide  Download

https://hal.inria.fr/hal-01162796
Contributor : Fatima Zahra Moataz <>
Submitted on : Thursday, June 11, 2015 - 1:54:27 PM
Last modification on : Friday, March 29, 2019 - 3:20:02 PM
Long-term archiving on : Tuesday, April 25, 2017 - 6:51:37 AM

File

PAFT_WGV0.pdf
Files produced by the author(s)

Identifiers

  • 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⟩

Share

Metrics

Record views

917

Files downloads

188