A Formalised Lower Bound on Undirected Graph Reachability

DOI10.1007/978-3-540-89439-1_43zbMATH Open1182.68107OpenAlexW1786859308MaRDI QIDQ5505585FDOQ5505585

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

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

• 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)