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

Improved fairness algorithms for rings with spatial reuse

Israel Cidon, Leonidas Georgiadis, et al.

IEEE/ACM Transactions on Networking

Paper

Distributed Code Assignments for CDMA Packet Radio Networks

Limin Hu

IEEE/ACM Transactions on Networking

Conference paper

Identity delegation in policy based systems

Rajeev Gupta, Shourya Roy, et al.

ICAC 2006

View all publications

Abstract

Related

Evolution of multiprotocol label switching

Improved fairness algorithms for rings with spatial reuse

Distributed Code Assignments for CDMA Packet Radio Networks

Identity delegation in policy based systems