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.

Paper

Evolution of multiprotocol label switching

Arun Viswanathan, Nancy Feldman, et al.

IEEE Communications Magazine

Paper

A global spatial similarity optimization scheme to track large numbers of dendritic spines in time-lapse confocal microscopy

Qing Li, Zhigang Deng, et al.

IEEE T-MI

Conference paper

Multiple range query optimization with distributed cache indexing

Beomseok Nam, Henrique Andrade, et al.

ACM/IEEE SC 2006

Paper

Routing and Wavelength Assignment in All-Optical Networks

Rajiv Ramaswami, Kumar N. Sivarajan

IEEE/ACM Transactions on Networking

View all publications

Abstract

Related

Evolution of multiprotocol label switching

A global spatial similarity optimization scheme to track large numbers of dendritic spines in time-lapse confocal microscopy

Multiple range query optimization with distributed cache indexing

Routing and Wavelength Assignment in All-Optical Networks