Random walks on weighted graphs, and applications to on-line algorithms.

D. Coppersmith; Peter Doyle; Prabhakar Raghavan; Marc Snir

doi:10.1145/100216.100266

STOC 1990

Conference paper

14 May 1990

Random walks on weighted graphs, and applications to on-line algorithms.

View publication

Abstract

We study the design and analysis of randomized on-line algorithms. We show that this problem is closely related to the synthesis of random walks on graphs with positive real costs on their edges.

Conference paper

Separator theorem for graphs with an excluded minor and its applications

N. Alon, Paul Seymour, et al.

STOC 1990

Conference paper

Web as a graph

R. Kumar, Prabhakar Raghavan, et al.

SIGMOD/PODS/ 2000

Paper

An Optimum Time Slot Assignment Algorithm for an SS/TDMA System with Variable Number of Transponders

G. Bongiovanni, D. Coppersmith, et al.

IEEE Transactions on Communications

Paper

Hypersearching the Web

Soumen Chakrabarti, B. Dom, et al.

Scientific American

View all publications

Abstract

Related

Separator theorem for graphs with an excluded minor and its applications

Web as a graph

An Optimum Time Slot Assignment Algorithm for an SS/TDMA System with Variable Number of Transponders

Hypersearching the Web