Random walks on weighted graphs and applications to on-line algorithms
From MaRDI portal
Publication:3140012
DOI10.1145/174130.174131zbMath0785.68071OpenAlexW1970647593WikidataQ57904592 ScholiaQ57904592MaRDI QIDQ3140012
Marc Snir, Don Coppersmith, Prabhakar Raghavan, Peter G. Doyle
Publication date: 9 December 1993
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/174130.174131
Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (31)
Competitive randomized algorithms for nonuniform problems ⋮ A deterministic \(O(k^ 3)\)-competitive \(k\)-server algorithm for the circle ⋮ Random walks on graphs with interval weights and precise marginals ⋮ Competitive algorithms for the weighted server problem ⋮ Asynchronous deterministic rendezvous in graphs ⋮ The weighted 2-server problem ⋮ Online perfect matching and mobile computing ⋮ Limit theorems and structural properties of the cat-and-mouse Markov chain and its generalisations ⋮ Randomized competitive analysis for two server problems ⋮ Random walks and the effective resistance sum rules ⋮ Competitive distributed decision-making ⋮ R-LINE: a better randomized 2-server algorithm on the line ⋮ Breaking the 2-competitiveness barrier for two servers in a tree ⋮ A scaling analysis of a cat and mouse Markov chain ⋮ The \(k\)-server problem ⋮ Potential induced random teleportation on finite graphs ⋮ Geometric two-server algorithms ⋮ On the advice complexity of the \(k\)-server problem under sparse metrics ⋮ On convex body chasing ⋮ Efficiency test of pseudorandom number generators using random walks ⋮ The combinatorics of effective resistances and resistive inverses ⋮ Random walks on a finite graph with congestion points ⋮ Competitive Algorithms for Layered Graph Traversal ⋮ Non-uniform random spanning trees on weighted graphs ⋮ Calculating effective resistances on underlying networks of association schemes ⋮ More on random walks, electrical networks, and the harmonic \(k\)-server algorithm. ⋮ Chaotic Traversal (CHAT): Very Large Graphs Traversal Using Chaotic Dynamics ⋮ On the power of randomization in on-line algorithms ⋮ Randomized competitive algorithms for the list update problem ⋮ On-line algorithms for locating checkpoints ⋮ Memoryless algorithms for the generalized k-server problem on uniform metrics
This page was built for publication: Random walks on weighted graphs and applications to on-line algorithms
