Searching Constant Width Mazes Captures the tex2html_wrap_inline17 Hierarchy

David A. Mix Barrington
Chi-Jen Lu
Peter Bro Miltersen
Sven Skyum

September 1997


We show that searching a width k maze is complete for tex2html_wrap_inline21 , i.e., for the k'th level of the tex2html_wrap_inline17 hierarchy. Equivalently, st-connectivity for width k grid graphs is complete for tex2html_wrap_inline21 . As an application, we show that there is a data structure solving dynamic st-connectivity for constant width grid graphs with time bound tex2html_wrap_inline31 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.


Last modified: 2003-06-08 by webmaster.