Planar and Grid Graph Reachability Problems
Article Properties
-
LanguageEnglish
-
DOI (url)
-
Publication Date2009/02/05
-
Journal
-
Indian UGC (journal)
-
Refrences41
-
Citations15
-
Eric Allender
-
David A. Mix Barrington
-
Tanmoy Chakraborty
-
Samir Datta
-
Sambuddha Roy
Cite
Allender, Eric, et al. “Planar and Grid Graph Reachability Problems”. Theory of Computing Systems, vol. 45, no. 4, 2009, pp. 675-23, https://doi.org/10.1007/s00224-009-9172-z.
Allender, E., Mix Barrington, D. A., Chakraborty, T., Datta, S., & Roy, S. (2009). Planar and Grid Graph Reachability Problems. Theory of Computing Systems, 45(4), 675-723. https://doi.org/10.1007/s00224-009-9172-z
Allender, Eric, David A. Mix Barrington, Tanmoy Chakraborty, Samir Datta, and Sambuddha Roy. “Planar and Grid Graph Reachability Problems”. Theory of Computing Systems 45, no. 4 (2009): 675-723. https://doi.org/10.1007/s00224-009-9172-z.
Allender E, Mix Barrington DA, Chakraborty T, Datta S, Roy S. Planar and Grid Graph Reachability Problems. Theory of Computing Systems. 2009;45(4):675-723.
Journal Categories
Science
Mathematics
Science
Mathematics
Instruments and machines
Electronic computers
Computer science
Science
Mathematics
Instruments and machines
Electronic computers
Computer science
Computer software
Technology
Electrical engineering
Electronics
Nuclear engineering
Electronics
Computer engineering
Computer hardware
Refrences
| Title | Journal | Journal Categories | Citations | Publication Date |
|---|---|---|---|---|
| Isolation, Matching, and Counting Uniform and Nonuniform Upper Bounds | Journal of Computer and System Sciences |
| 23 | 1999 |
| Faster Shortest-Path Algorithms for Planar Graphs | Journal of Computer and System Sciences |
| 118 | 1997 |
| Counting Quantifiers, Successor Relations, and Logarithmic Space | Journal of Computer and System Sciences |
| 30 | 1997 |
| An Optimal Parallel Algorithm for Formula Evaluation | SIAM Journal on Computing |
| 27 | 1992 |
| 10.1016/0196-6774(92)90004-V | Journal of Algorithms | 1992 |
Citations
| Title | Journal | Journal Categories | Citations | Publication Date |
|---|---|---|---|---|
| Space-efficient algorithms for reachability in directed geometric graphs | Theoretical Computer Science |
| 2023 | |
| Depth-first search in directed planar graphs, revisited | Acta Informatica |
| 1 | 2022 |
Planar Graph Isomorphism Is in Log-Space | ACM Transactions on Computation Theory |
| 2022 | |
| On the complexity of two-dimensional signed majority cellular automata | Journal of Computer and System Sciences |
| 8 | 2018 |
Min/Max-Poly Weighting Schemes and the NL versus UL Problem | ACM Transactions on Computation Theory |
| 2017 |
Citations Analysis
The category
Science: Mathematics: Instruments and machines: Electronic computers. Computer science 14
is the most commonly referenced area in studies that cite this article. The first research to cite this article was titled Logspace Reduction of Directed Reachability for Bounded Genus Graphs to the Planar Case and was published in 2010. The most recent citation comes from a 2023 study titled Space-efficient algorithms for reachability in directed geometric graphs. This article reached its peak citation in 2013, with 3 citations. It has been cited in 9 different journals, 11% of which are open access. Among related journals, the ACM Transactions on Computation Theory cited this research the most, with 6 citations. The chart below illustrates the annual citation trends for this article.