Random Structures and Algorithms, Volume 7

Volume 7, Number 1, August 1995

Luc Devroye, Jiang Lu: The Strong Convergence of Maximal Degrees in Uniform Random Recursive Trees and Dags. 1-14 BibTeX
Jan Krajícek, Pavel Pudlák, Alan R. Woods: An Exponenetioal Lower Bound to the Size of Bounded Depth Frege Proofs of the Pigeonhole Principle. 15-40 BibTeX
Alan M. Frieze, Svante Janson: Perfect Matchings in Random s-Uniform Hypergraphs. 41-58 BibTeX
Anil Kamath, Rajeev Motwani, Krishna V. Palem, Paul G. Spirakis: Tail Bounds for Occupancy and the Satisfiability Threshold Conjecture. 59-80 BibTeX
Werner Schachinger: The Variance of Partial Match Retrieval in a Multidimensional Symmetric Trie. 81-96 BibTeX

Richard M. Karp, Yanjun Zhang: Bounded Branching Process AND/OR Tree Evaluation. 97-116 BibTeX
Philippe Flajolet, Gilbert Labelle, Louise Laforest, Bruno Salvy: Hypergeometrics and the Cost Structure of Quadtrees. 117-144 BibTeX
Michael Krivelevich: Bounding Ramsey Numbers through Large Deviation Inequalities. 145-156 BibTeX
Mark Jerrum: A Very Simple Algorithm for Estimating the Number of k-Colorings of a Low-Degree Graph. 157-166 BibTeX
Joel Spencer: Asymptotic Packing via a Branching Process. 167-172 BibTeX

Jeong Han Kim: The Ramsey Number R(3, t) Has Order of Magnitude t₂/log t. 173-208 BibTeX
Michael Molloy, Bruce A. Reed: The Dominating Number of Random Cubic Graph. 209-222 BibTeX
Dwight Duffus, Mark Ginn, Vojtech Rödl: On the Computational Complexity of Ordered Subgraph Recognition. 223-268 BibTeX
James B. Shearer: On the Independence Number of Sparse Graphs. 269-272 BibTeX

Edward A. Bender, L. Bruce Richmond, Nicholas C. Wormald: Largest 4-Connected Components of 3-Connected Planar Triangulations. 273-286 BibTeX
Catherine C. McGeoch, J. D. Tygar: Optimal Sampling Strategies for Quicksort. 287-300 BibTeX
Jin-yi Cai, Suresh Chari: On the Impossibility of Amplifying the Independence of Random Variables. 301-310 BibTeX
Svante Janson: The Minimal Spanning Tree in a Complete Graph and a Functional Limit Theorem for Trees in a Random Graph. 337-356 BibTeX