Time--Space Tradeoffs For Undirected st-Connectivity on a Graph Automata

DOI10.1137/S0097539794277135zbMath0907.68125OpenAlexW1995738188MaRDI QIDQ4210119

Jeff Edmonds

Publication date: 21 September 1998

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

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

zbMATH Keywords

lower boundstime-space tradeoffsundirected st-connectivityJAG graph

Mathematics Subject Classification ID

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

This page was built for publication: Time--Space Tradeoffs For Undirected st-Connectivity on a Graph Automata