Random Structures and Algorithms, Volume 15

Volume 15, Number 1, August 1999

Guy Louchard: Probabilistic analysis of column-convex and directed diagonally-convex animals. II: Trajectories and shapes. 1-23
Ralph Neininger, Ludger Rüschendorf: On the internal path length of d-dimensional quad trees. 25-41
Hans Garmo: The asymptotic distribution of long cycles in random regular graphs. 43-92
Tom Bohman, Janko Gravner: Random threshold growth dynamics. 93-111

Don Coppersmith, Gregory B. Sorkin: Constructive bounds and exact expectations for the random assignment problem. 113-144
Mathew D. Penrose: On k-connectivity for a geometric random graph. 145-164
Wansoo T. Rhee: Some exact rates for the random weighted interval packing problem. 165-175
David Aldous, Jim Pitman: A family of random trees with random edge lengths. 176-195
Heinrich Matzinger: Reconstructing a three-color scenery by observing it along a simple random walk path. 196-207

Statistical Physics Methods in Discrete Probability, Combinatorics, and Theoretical Computer Science

Jennifer T. Chayes, Dana Randall: Foreword. 209
Dominic Welsh: The Tutte polynomial. 210-228
Michael Luby, Eric Vigoda: Fast convergence of the Glauber dynamics for sampling independent sets. 229-241
Colin Cooper, Alan M. Frieze: Mixing properties of the Swendsen-Wang process on classes of graphs. 242-261
S. Nanda, Charles M. Newman: Random nearest neighbor and influence graphs on Z^d. 262-278
Boris Pittel, Robert S. Weishaar: The random bipartite nearest neighbor graphs. 279-310
Olle Häggström, Robin Pemantle: On near-critical and dynamical percolation in the tree case. 311-318
Michael Aizenman, Almut Burchard, Charles M. Newman, David Bruce Wilson: Scaling limits for minimal and random spanning trees in two dimensions. 319-367
Christian Borgs, Jennifer T. Chayes, Harry Kesten, Joel Spencer: Uniform boundedness of critical crossing probabilities implies hyperscaling. 368-413
Rémi Monasson, Riccardo Zecchina, Scott Kirkpatrick, Bart Selman, Lidror Troyansky: 2+p-SAT: Relation of typical-case complexity to the nature of the phase transition. 414-435
Michel Talagrand: Intersecting random half cubes. 436-449
Richard M. Karp, Claire Kenyon, Orli Waarts: Error-resilient DNA computation. 450-466