A Time-Space Tradeoff for Undirected Graph Traversal by Walking Automata

DOI10.1137/S0097539793282947zbMath0928.68085MaRDI QIDQ4229423

Prabhakar Raghavan, Allan Borodin, Walter L. Ruzzo, Martin Tompa, P. W. Beame

Publication date: 22 February 1999

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

zbMATH Keywords

graph connectivity; time-space tradeoff; graph reachability; JAG; jumping automaton; walking automaton

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68W05: Nonnumerical algorithms

68Q10: Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.)

68R10: Graph theory (including graph drawing) in computer science

68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)

05C40: Connectivity

Related Items

A space lower bound for \(st\)-connectivity on node-named JAGs