Time-space tradeoffs for undirected graph traversal by graph automata

DOI10.1006/INCO.1996.0085zbMATH Open0872.68067OpenAlexW1982053238WikidataQ57904581 ScholiaQ57904581MaRDI QIDQ675049FDOQ675049

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

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

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)

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
• A Formalised Lower Bound on Undirected Graph Reachability
• Irredundant algorithms for traversing directed graphs: The deterministic case
• Finite graph automata for linear and boundary graph languages
• Title not available (Why is that?)
• Undirected \(s\)--\(t\) connectivity in polynomial time and sublinear space

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)