Name
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 NC^1 under AC^0 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. [14], 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. |
Year | DOI | Venue |
|---|---|---|
2005 | 10.1109/CCC.2006.22 | Electronic Colloquium on Computational Complexity |
Keywords | DocType | ISSN |
natural example,various class,series-parallel digraph,grid graph reachability problems,certain class,grid graph,• reachability on grid graphs is logspace-equivalent to reachability in general planar digraphs,reachability problem,and,directed graphs,computational complexity,series parallel | Journal | 1093-0159 |
ISBN | Citations | PageRank |
0-7695-2596-2 | 15 | 0.89 |
References | Authors | |
18 | 5 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Eric Allender | 1 | 1434 | 121.38 |
| David A. Mix Barrington | 2 | 25 | 1.78 |
| Tanmoy Chakraborty | 3 | 466 | 76.71 |
| Samir Datta | 4 | 200 | 19.82 |
| Sambuddha Roy | 5 | 219 | 19.23 |