Random Structures and Algorithms, Volume 16

Volume 16, Number 1, January 2000

Michal Karonski, Joel Spencer: Ten Years! 1-3
Jaikumar Radhakrishnan, Aravind Srinivasan: Improved bounds and algorithms for hypergraph 2-coloring. 4-32
Colin Cooper, Alan M. Frieze, Kurt Mehlhorn, Volker Priebe: Average-case complexity of shortest-paths problems in the vertex-potential model. 33-46
Zhicheng Gao, Brendan D. McKay, Xiaoji Wang: Asymptotic enumeration of tournaments with a given score sequence containing a specified digraph. 47-57
Peter Winkler: Dependent percolation and colliding random walks. 58-84 David Bruce Wilson: How to couple from the past using a read-once source of randomness. 85-113

Johan Jonasson: Lollipop graphs are extremal for commute times. 131-142
Christopher Hoffman: Energy of flows on Z2 percolation clusters. 143-155
James Allen Fill, Edward R. Scheinerman, Karen B. Singer-Cohen: Random intersection graphs when m=omega(n): An equivalence theorem relating the evolution of the G(n, m, p) and G(n, p) models. 156-176
Yoshiharu Kohayakawa, Bernd Kreuter, Deryk Osthus: The length of random subsets of Boolean lattices. 177-194
Uriel Feige, Robert Krauthgamer: Finding and certifying a large hidden clique in a semirandom graph. 195-208
Colin Cooper: On the rank of random matrices. 209-232

Petr Savický: On random orderings of variables for parity ordered binary decision diagrams. 233-239
Susanne Albers, Michael Mitzenmacher: Average-case analyses of first fit and random fit bin packing. 240-259
Tomasz Luczak: On triangle-free random graphs. 260-276
Stéphane Boucheron, Gábor Lugosi, Pascal Massart: A sharp concentration inequality with applications. 277-292

Claudia Bertram-Kretzberg, Hanno Lefmann: MOD_p-tests, almost independence and small probability spaces. 293-313
Wenceslas Fernandez de la Vega, Marek Karpinski: Polynomial time approximation of dense weighted instances of MAX-CUT. 314-332
Johan Jonasson, Elchanan Mossel, Yuval Peres: Percolation in a dependent random environment. 333-343
Van H. Vu: On the concentration of multivariate polynomials with small expectation. 344-363
Noga Alon: Degrees and choice numbers. 364-368
Colin Cooper, Alan M. Frieze: Hamilton cycles in random graphs and directed graphs. 369-401