Space Complexity of Reachability Testing in Labelled Graphs

DOI10.1007/978-3-319-53733-7_26MaRDI QIDQ5739010zbMATH OpenOpenAlexFDO

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

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) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Graph labelling (graceful graphs, bandwidth, etc.) (05C78)

Recommendations

• Space complexity of reachability testing in labelled graphs
• Space complexity of the directed reachability problem over surface-embedded graphs
• On the time-space complexity of reachability queries for preprocessed graphs
• Complexity of testing reachability in matroids
• scientific article; zbMATH DE number 7765385
• Space-efficient algorithms for reachability in directed geometric graphs
• scientific article; zbMATH DE number 7650245
• A Formalised Lower Bound on Undirected Graph Reachability

Cites work

• scientific article; zbMATH DE number 1223708 (Why is no real title available?)
• scientific article; zbMATH DE number 2077108 (Why is no real title available?)
• Computational Complexity
• Directed planar reachability is in unambiguous log-space
• Excluding a group-labelled graph
• Extensions to Barrington's M-program model
• Finite Monoids: From Word to Circuit Evaluation
• Finite loops recognize exactly the regular open languages
• Finite monoids and the fine structure of NC ¹
• Locally trivial categories and unambiguous concatenation
• Log-space algorithms for paths and matchings in \(k\)-trees
• On the complexity of L-reachability
• On the sequential nature of interprocedural program-analysis problems
• Pseudorandom walks on regular digraphs and the RL vs. L problem
• Reachability Problems: An Update
• Unbounded fan-in circuits and associative functions
• Undirected connectivity in log-space

Cited in

(4)

• On the complexity of L-reachability
• On the complexity of L-reachability
• Exponential space complexity for OBDD-based reachability analysis
• Space complexity of reachability testing in labelled graphs

This page was built for publication: Space Complexity of Reachability Testing in Labelled Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5739010)