A Formalised Lower Bound on Undirected Graph Reachability
DOI10.1007/978-3-540-89439-1_43zbMATH Open1182.68107OpenAlexW1786859308MaRDI QIDQ5505585FDOQ5505585
Authors: Ulrich Schöpp 
Publication date: 27 January 2009
Published in: Logic for Programming, Artificial Intelligence, and Reasoning (Search for Journal in Brave)
Full work available at URL: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.210.865
Recommendations
- Time--Space Lower Bounds for Directed st-Connectivity on Graph Automata Models
- scientific article; zbMATH DE number 1414308
- A space lower bound for \(st\)-connectivity on node-named JAGs
- Directed planar reachability is in unambiguous log-space
- Time-space tradeoffs for undirected graph traversal by graph automata
Formal languages and automata (68Q45) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Cited In (5)
- Space Complexity of Reachability Testing in Labelled Graphs
- Title not available (Why is that?)
- An $$O(n^{\epsilon })$$ Space and Polynomial Time Algorithm for Reachability in Directed Layered Planar Graphs
- An O ( n ϵ ) Space and Polynomial Time Algorithm for Reachability in Directed Layered Planar Graphs
- Space complexity of reachability testing in labelled graphs
Uses Software
This page was built for publication: A Formalised Lower Bound on Undirected Graph Reachability
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5505585)
