| |
1-9 of 9 reviews |
Date Reviewed | |
| |
Edge flows in the complete random-lengths network
Aldous D., Bhamidi S. Random Structures & Algorithms 37(3): 271-311, 2010. Type: Article
A network is an undirected graph whose edges have positive real edge-lengths. The purpose of this paper is to prove that a random measure on suitably defined networks converges to a fixed measure....
|
Feb 14 2011 |
|
| |
Randomly coloring random graphs
Dyer M., Frieze A. Random Structures & Algorithms 36(3): 251-272, 2010. Type: Article
The problem of coloring random graphs is a well-known problem in computer science that has received ample attention. The problem consists of finding an assignment of colors--from a predefined set--for all vertices of ...
|
Jul 8 2010 |
|
| |
Vertex and edge expansion properties for rapid mixing
Montenegro R. Random Structures & Algorithms 26(1-2): 52-68, 2005. Type: Article
Houdré and Tetali [1] considered the discrete gradients (x), a family which involves all three properties of the new rapid mixing (with regard to edges) ver...
|
Nov 11 2005 |
|
| |
Identifying several biased coins encountered by a hidden random walk
Levin D., Peres Y. Random Structures & Algorithms 25(1): 91-114, 2004. Type: Article
Levin and Peres consider a coin tossing experiment where &thgr;(z) &egr; [0,1] is associated with each integer z. If the position of the random walker is Sn, a...
|
Mar 23 2005 |
|
| |
Some bounds on the coupon collector problem
Martinez S. Random Structures & Algorithms 25(2): 208-226, 2004. Type: Article
Martinez considers the famous coupon collector problem, in which coupons are drawn with replacement from the set {1,2,3,...,n}, and establishes a ratio limit theorem for the random time T required ...
|
Feb 23 2005 |
|
| |
The Wiener index of simply generated random trees
Janson S. Random Structures & Algorithms 22(4): 337-358, 2003. Type: Article
The Wiener index W(G) of a connected graph G is the sum of all of the distances between pairs of vertices of G. This index was introduced in 1947 by the chemist Harry Wiener for ...
|
May 14 2004 |
|
| |
Three theorems regarding testing graph properties
Goldreich O., Trevisan L. Random Structures & Algorithms 23(1): 23-57, 2003. Type: Article
Goldreich and Trevisan present results concerning graph properties in the adjacency matrix representation. A graph property π is monotone if any supergraph of a graph that has the property π also has property π. Th...
|
Oct 16 2003 |
|
| |
Deterministic approximation of the cover time
Feige U., Rabinovich Y. Random Structures & Algorithms 23(1): 1-22, 2003. Type: Article
Feige and Rabinovich propose an algorithm for the deterministic approximation of the cover time of reversible Markov chains. Most of the current approaches deal with upper and lower bounds for cover time that hold for any size-
|
Oct 7 2003 |
|
| |
The decomposition threshold for bipartite graphs with minimum degree one
Yuster R. Random Structures & Algorithms 21(2): 121-134, 2002. Type: Article
In previous work, the author was able to show the asymptotic behavior of trees, with respect to graph decompositions. In this paper, the author extends his work by investigating bipartite graphs with minimum degree one....
|
Jul 29 2003 |
|
| |
|
|
| |
|
|
|
|
