A Formalised Lower Bound on Undirected Graph Reachability

DOI10.1007/978-3-540-89439-1_43MaRDI QIDQ5505585zbMATH OpenOpenAlexFDO

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

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Formal languages and automata (68Q45) Graph theory (including graph drawing) in computer science (68R10)

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

Cited in

(5)

• Space complexity of reachability testing in labelled graphs
• 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
• scientific article; zbMATH DE number 7650316 (Why is no real title available?)

Describes a project that uses

Uses Software

• Coq
• Coq/SSReflect

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)