Abstract: A transition in a graph is a pair of adjacent edges. Given a graph $$G=V,E$$, a set of forbidden transitions $$\mathcal{F}\subseteq E\times E$$ and two vertices $$s,t \in V$$, we study the problem of finding a path from s to t which uses none of the forbidden transitions of $$\mathcal F$$. This means that it is forbidden for the path to consecutively use two edges forming a pair ini¾?$$\mathcal 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 ro...
(read more)
Topics: 
Combinatorics
Discrete mathematics