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

Analytics for resiliency in the mainframe

Liat Ein-Dor, Y. Goldschmidt, et al.

IBM J. Res. Dev

Conference paper

Self-assembling materials for lithographic patterning: Overview, status and moving forward

William Hinsberg, Joy Cheng, et al.

SPIE Advanced Lithography 2010

Paper

Fast geometric approximation techniques and geometric embedding problems

Marshall W. Bern, Howard J. Karloff, et al.

Theoretical Computer Science

Paper

Prioritizing a portfolio of information technology investment projects

Indranil R. Bardhan, Sugato Bagchi, et al.

JMIS

View all publications

Abstract

Related

Analytics for resiliency in the mainframe

Self-assembling materials for lithographic patterning: Overview, status and moving forward

Fast geometric approximation techniques and geometric embedding problems

Prioritizing a portfolio of information technology investment projects