Random Structures and Algorithms, Volume 1

Volume 1, Number 1, Spring 1990

Donald E. Knuth, Rajeev Motwani, Boris Pittel: Stable Husbands. 1-14 BibTeX
Svante Janson: A Functional Limit Theorem for Random Graphs with Applications to Subgraph Count Statistics. 15-38 BibTeX
Neil J. Calkin, Alan M. Frieze: Probabilistic Analysis of a Parallel Algorithm for Finding Maximal Independent Sets. 39-50 BibTeX
Persi Diaconis, Ronald L. Graham, John A. Morrison: Asymptotic Analysis of a Random Walk on a Hypercube with Many Dimensions. 51-72 BibTeX
Richard M. Karp: The Transitive Closure of a Random Digraph. 73-94 BibTeX
Béla Bollobás: Complete Matchings in Random Subgraphs on the Cube. 95-104 BibTeX
Fan R. K. Chung, Ronald L. Graham: Quasi-Random Hypergraphs. 105-124 BibTeX

Edward A. Bender, E. Rodney Canfield, Brendan D. McKay: The Asymptotic Number of Labeled Connected Graphs with a Given Number of Vertices and Edges. 127-170 BibTeX
Tomasz Luczak: On the Number of Sparse Connected Graphs. 171-174 BibTeX
Noga Alon: The Number of Spanning Trees in Regular Graphs. 175-182 BibTeX
Zoltán Füredi: Competition Graphs and Clique Dimensions. 183-190 BibTeX
Luc Devroye: On the Height of Random m-ary Search Trees. 191-204 BibTeX
Joel Spencer: Countable Sparse Random Graphs. 205-214 BibTeX
Géza Bohus: On the Discrepancy of 3 Permutations. 215-220 BibTeX
Svante Janson: Poisson Approximation for Large Deviations. 221-230 BibTeX
Stephen Suen: A correlation inequality and a Poisson limit theorem for nonoverlapping balanced subgraphs of a random graph. 231-242 BibTeX

Paul Erdös, Prasad Tetali: Representations of Integers as the Sum of k Terms. 245-262 BibTeX
Graham Brightwell, Peter Winkler: Maximum itting Time for Random Wlaks on Graphs. 263-276 BibTeX
Alexandr V. Kostochka: Matchings in Random Spanning Subgraphs of Cubelike Graphs. 277-286 BibTeX
Tomasz Luczak: Component Behavior Near the Critical Point of the Random Graph Process. 287-310 BibTeX
Boris Pittel: On Tree Census and the Giant Component in Sparse Random Graphs. 311-342 BibTeX
Zoltán Szabó: An Application of Lovász's Local Lemma - A New Lower Bound for the van der Waerden Number. 343-360 BibTeX

Fan R. K. Chung: Quasi-Random Classes of Hypergraphs. 363-382 BibTeX
David Aldous: A Random Tree Model Associated with Random Graphs. 383-402 BibTeX
Andrew D. Barbour, Svante Janson, Michal Karonski, Andrzej Rucinski: Small Cliques in Random Graphs. 403-434 BibTeX
Colin McDiarmid: On the Chromatic Number of Random Graphs. 435-442 BibTeX
Colin McDiarmid, Bruce A. Reed: Linear Arboricity of Random Regular Graphs. 443-447 BibTeX
Uriel Feige, David Peleg, Prabhakar Raghavan, Eli Upfal: Randomized Broadcast in Networks. 447-460 BibTeX