Random Structures and Algorithms, Volume 16

Volume 16, Number 1, January 2000

Michal Karonski, Joel Spencer: Ten Years! 1-3 BibTeX
Jaikumar Radhakrishnan, Aravind Srinivasan: Improved bounds and algorithms for hypergraph 2-coloring. 4-32 BibTeX
Colin Cooper, Alan M. Frieze, Kurt Mehlhorn, Volker Priebe: Average-case complexity of shortest-paths problems in the vertex-potential model. 33-46 BibTeX
Zhicheng Gao, Brendan D. McKay, Xiaoji Wang: Asymptotic enumeration of tournaments with a given score sequence containing a specified digraph. 47-57 BibTeX
Peter Winkler: Dependent percolation and colliding random walks. 58-84 BibTeX 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 BibTeX
Christopher Hoffman: Energy of flows on Z2 percolation clusters. 143-155 BibTeX
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 BibTeX
Yoshiharu Kohayakawa, Bernd Kreuter, Deryk Osthus: The length of random subsets of Boolean lattices. 177-194 BibTeX
Uriel Feige, Robert Krauthgamer: Finding and certifying a large hidden clique in a semirandom graph. 195-208 BibTeX
Colin Cooper: On the rank of random matrices. 209-232 BibTeX

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

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