Abstract:
We show that searching a width k maze is complete for
, i.e., for the k'th level of the hierarchy. Equivalently,
st-connectivity for width k grid graphs is complete for . As an
application, we show that there is a data structure solving dynamic
st-connectivity for constant width grid graphs with time bound per operation on a random access machine. The dynamic algorithm is
derived from the parallel one in an indirect way using algebraic
tools
Available as PostScript,
PDF.
|