Time-space tradeoffs for undirected graph traversal by graph automata

DOI10.1006/inco.1996.0085zbMath0872.68067OpenAlexW1982053238WikidataQ57904581 ScholiaQ57904581MaRDI QIDQ675049

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

Publication date: 13 October 1997

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/a56abd0944bf5cc19d3c8e56a60509c89063101e

zbMATH Keywords

undirected graph problems

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Related Items (5)

A spectrum of time-space trade-offs for undirected \(s-t\) connectivity ⋮ Regular languages with variables on graphs ⋮ Undirected \(s\)--\(t\) connectivity in polynomial time and sublinear space ⋮ Finite graph automata for linear and boundary graph languages ⋮ Voronoi-like nondeterministic partition of a lattice by collectives of finite automata

This page was built for publication: Time-space tradeoffs for undirected graph traversal by graph automata