Space complexity of reachability testing in labelled graphs
DOI10.1016/j.jcss.2019.04.002zbMath1425.68322OpenAlexW2945096684MaRDI QIDQ2316928
K. S. Sunil, Vidhya Ramaswamy, M. N. Jayalal Sarma
Publication date: 7 August 2019
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.jcss.2019.04.002
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Cites Work
- Unnamed Item
- Unnamed Item
- Log-space algorithms for paths and matchings in \(k\)-trees
- Unbounded fan-in circuits and associative functions
- Locally trivial categories and unambiguous concatenation
- Symmetric space-bounded computation
- Extensions to Barrington's M-program model
- Finding a path with two labels forbidden in group-labeled graphs
- Excluding a group-labelled graph
- On the sequential nature of interprocedural program-analysis problems
- Pseudorandom walks on regular digraphs and the RL vs. L problem
- Directed Planar Reachability Is in Unambiguous Log-Space
- Undirected connectivity in log-space
- Finite monoids and the fine structure of NC 1
- Finite loops recognize exactly the regular open languages
- On the Complexity of L-reachability*
- Computational Complexity
- Reachability Problems: An Update
This page was built for publication: Space complexity of reachability testing in labelled graphs
