Grid graph reachability problems

Eric Allender, Tanmoy Chakraborty, David A.Mix Barrington, Samir Datta, Sambuddha Roy

Research output: Chapter in Book/Report/Conference proceedingConference contribution

10 Scopus citations

Abstract

We study the complexity of reachability problems on various classes of grid graphs. Reachability on certain classes of grid graphs gives natural examples of problems that are hard for NC1 under AC0 reductions but are not known to be hard for L; they thus give insight into the structure of L. In addition to explicating the structure of L, another of our goals is to expand the class of digraphs for which connectivity can be solved in logspace, by building on the work of Jakoby et al. 114], who showed that reachability in series-parallel digraphs is solvable in L. We show that reachability for single-source multiple-sink planar dags is solvable in L.

Original languageEnglish (US)
Title of host publicationProceedings - Twenty-First Annual IEEE Conference on Computational Complexity, CCC 2006
Pages299-313
Number of pages15
DOIs
StatePublished - Dec 1 2006
Event21st Annual IEEE Conference on Computational Complexity, CCC 2006 - Prague, Czech Republic
Duration: Jul 16 2006Jul 20 2006

Publication series

NameProceedings of the Annual IEEE Conference on Computational Complexity
Volume2006
ISSN (Print)1093-0159

Other

Other21st Annual IEEE Conference on Computational Complexity, CCC 2006
CountryCzech Republic
CityPrague
Period7/16/067/20/06

All Science Journal Classification (ASJC) codes

  • Software
  • Theoretical Computer Science
  • Computational Mathematics

Fingerprint Dive into the research topics of 'Grid graph reachability problems'. Together they form a unique fingerprint.

Cite this