Time-space tradeoffs for undirected graph traversal by graph automata

DOI10.1006/INCO.1996.0085MaRDI QIDQ675049zbMATH OpenOpenAlexWikidataFDO

Authors Allan Borodin, Prabhakar Raghavan, Walter L. Ruzzo, Martin Tompa, Paul 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)

Recommendations

• Time--Space Tradeoffs For Undirected st-Connectivity on a Graph Automata
• Trading Space for Time in Undirected s-t Connectivity
• A spectrum of time-space trade-offs for undirected s-t connectivity

Cited in

(8)

• Regular languages with variables on graphs
• Voronoi-like nondeterministic partition of a lattice by collectives of finite automata
• A spectrum of time-space trade-offs for undirected \(s-t\) connectivity
• Undirected \(s\)--\(t\) connectivity in polynomial time and sublinear space
• Irredundant algorithms for traversing directed graphs: The deterministic case
• scientific article; zbMATH DE number 3911721 (Why is no real title available?)
• A Formalised Lower Bound on Undirected Graph Reachability
• Finite graph automata for linear and boundary graph languages

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

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