A time-space tradeoff for undirected graph traversal by walking automata

Paul Beame; Allan Borodin; Prabhakar Raghavan; Walter L. Ruzzo; Martin Tompa

doi:10.1137/s0097539793282947

SIAM Journal on Computing

Paper

01 Jan 1999

A time-space tradeoff for undirected graph traversal by walking automata

View publication

Abstract

We prove a time-space tradeoff for traversing undirected graphs, using a structured model that is a nonjumping variant of Cook and Rackoff's "jumping automata for graphs.". © 1999 Society for Industrial and Applied Mathematics.

Conference paper

Multiple range query optimization with distributed cache indexing

Beomseok Nam, Henrique Andrade, et al.

ACM/IEEE SC 2006

Conference paper

Measurement, modeling, and analysis of internet video sharing site workload: A case study

Xiaozhu Kang, Hui Zhang, et al.

ICWS 2008

Paper

Automated Learning of Decision Rules for Text Categorization

Chidanand Apté, Fred Damerau, et al.

ACM Transactions on Information Systems (TOIS)

Paper

Routing and Wavelength Assignment in All-Optical Networks

Rajiv Ramaswami, Kumar N. Sivarajan

IEEE/ACM Transactions on Networking

View all publications

Abstract

Related

Multiple range query optimization with distributed cache indexing

Measurement, modeling, and analysis of internet video sharing site workload: A case study

Automated Learning of Decision Rules for Text Categorization

Routing and Wavelength Assignment in All-Optical Networks