Space Complexity of Reachability Testing in Labelled Graphs

DOI10.1007/978-3-319-53733-7_26zbMath1425.68321OpenAlexW2589069383MaRDI QIDQ5739010

M. N. Jayalal Sarma, K. S. Sunil, Vidhya Ramaswamy

Publication date: 1 June 2017

Published in: Language and Automata Theory and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-53733-7_26

Mathematics Subject Classification ID

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
• Unnamed Item
• Unbounded fan-in circuits and associative functions
• Locally trivial categories and unambiguous concatenation
• 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 ¹
• Finite Monoids: From Word to Circuit Evaluation
• 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