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.

Invited talk

In-memory computing based on phase-change memory

Conference paper

Fusing Modalities by Multiplexed Graph Neural Networks for Outcome Prediction in Tuberculosis

Paper

Combining explainable machine learning, demographic and multi-omic data to inform precision medicine strategies for inflammatory bowel disease

Workshop paper

Privacy-preserving record linkage using local sensitive hash and private set intersection

View all publications

Abstract

Related

In-memory computing based on phase-change memory

Fusing Modalities by Multiplexed Graph Neural Networks for Outcome Prediction in Tuberculosis

Combining explainable machine learning, demographic and multi-omic data to inform precision medicine strategies for inflammatory bowel disease

Privacy-preserving record linkage using local sensitive hash and private set intersection