Time--Space Lower Bounds for Directed st-Connectivity on Graph Automata Models

DOI10.1137/S0097539795294402MaRDI QIDQ4210090zbMATH OpenOpenAlexFDO

Authors Greg Barnes, Jeff Edmonds

Publication date 20 September 1998

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/s0097539795294402

zbMATH Keywords

JAG graph st-connectivitylower boundstime-space tradeoffs

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• scientific article; zbMATH DE number 1263190
• Time--Space Tradeoffs For Undirected st-Connectivity on a Graph Automata
• A space lower bound for \(st\)-connectivity on node-named JAGs

Cited in

(7)

• A space lower bound for \(st\)-connectivity on node-named JAGs
• Directed st-Connectivity Is Not Expressible in Symmetric Datalog
• Undirected ST-connectivity in log-space
• Time--Space Tradeoffs For Undirected st-Connectivity on a Graph Automata
• scientific article; zbMATH DE number 1263190 (Why is no real title available?)
• Tight Lower Bounds for st-Connectivity on the NNJAG Model
• A Formalised Lower Bound on Undirected Graph Reachability

This page was built for publication: Time--Space Lower Bounds for Directed st-Connectivity on Graph Automata Models

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