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

Tight bounds for delay-sensitive aggregation

Yvonne Anne Pignolet, Stefan Schmid, et al.

Discrete Mathematics and Theoretical Computer Science

Workshop paper

MulticoreSDK: A practical and efficient data race detector for real-world applications

Yao Qi, Raja Das, et al.

ISSTA 2009

Conference paper

Placement of multimedia blocks on zoned disks

Renu Tewari, Richard P. King, et al.

IS&T/SPIE Electronic Imaging 1996

Paper

A list-oriented extension of the lambda-calculus satisfying the Church-Rosser theorem

György E. Révész

Theoretical Computer Science

View all publications

Abstract

Related

Tight bounds for delay-sensitive aggregation

MulticoreSDK: A practical and efficient data race detector for real-world applications

Placement of multimedia blocks on zoned disks

A list-oriented extension of the lambda-calculus satisfying the Church-Rosser theorem