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

DOI10.1137/S0097539793282947zbMath0928.68085OpenAlexW2043088202MaRDI QIDQ4229423

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

Publication date: 22 February 1999

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

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

zbMATH Keywords

graph connectivitytime-space tradeoffgraph reachabilityJAGjumping automatonwalking automaton

Mathematics Subject Classification ID

Related Items (2)

Lifting query complexity to time-space complexity for two-way finite automata ⋮ A space lower bound for \(st\)-connectivity on node-named JAGs

This page was built for publication: A Time-Space Tradeoff for Undirected Graph Traversal by Walking Automata