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

Prior derivation models for formally syntax-based translation using linguistically syntactic parsing and tree kernels

Bowen Zhou, Bing Xiang, et al.

SSST 2008

Conference paper

Placement of multimedia blocks on zoned disks

Renu Tewari, Richard P. King, et al.

IS&T/SPIE Electronic Imaging 1996

Conference paper

HealthSense: Classification of health-related sensor data through user-assisted machine learning

Erich P. Stuntebeck, John S. Davis II, et al.

HotMobile 2008

Paper

The use of AI in construction financing for private customers

Oliver Bodemer

IBM J. Res. Dev

View all publications

Abstract

Related

Prior derivation models for formally syntax-based translation using linguistically syntactic parsing and tree kernels

Placement of multimedia blocks on zoned disks

HealthSense: Classification of health-related sensor data through user-assisted machine learning

The use of AI in construction financing for private customers