On reachability in graphs with obstacles
Udit Agarwal, Kalpesh Kapoor · Discrete Mathematics Algorithms and Applications · 2015
Given a graph, [Formula: see text], a configuration of [Formula: see text] represents that there is a robot at a vertex and obstacles at some other vertices. The remaining vertices of [Formula: see text] not having the robot or an obstacle are said to be empty. The robot or an obstacle can be moved from its place to an adjacent vertex if it is empty. We give two definitions of reachability and show that they are equivalent in case of undirected graphs. We give an [Formula: see text] time algorithm for computing the minimum value of [Formula: see text] for [Formula: see text]-reachability in undirected graphs. However, we show that the two notions of reachability are different in case of directed graphs. We present a linear time algorithm for computing the minimum value of [Formula: see text] for [Formula: see text]-reachability in directed trees.