Random Structures and Algorithms, Volume 20

Volume 20, Number 1, January 2002

• Alon Amit, Nathan Linial, Jirí Matousek: Random lifts of graphs: Independence and chromatic number. 1-22
• Ricardo A. Baeza-Yates, Gonzalo Navarro: New and faster filters for multiple approximate string matching. 23-49
• Bae-Shi Huang, Ljubomir Perkovic, Eric Schmutz: Inexpensive d-dimensional matchings. 50-58
• Jason Schweinsberg: An O(n²) bound for the relaxation time of a Markov chain on cladograms. 59-70
• Alexander Gnedin, Sergei Kerov: Fibonacci solitaire. 71-88
• Paul Balister: Vertex-distinguishing edge colorings of random graphs. 89-97
• Martin E. Dyer, Catherine S. Greenhill, Michael Molloy: Very rapid mixing of the Glauber dynamics for proper colorings on bounded-degree graphs. 98-114
• Jean-François Marckert, Alois Panholzer: Noncrossing trees are almost conditioned Galton-Watson trees. 115-125
• Tom Bohman, Alan M. Frieze: Addendum to avoiding a giant component. 126-130

Volume 20, Number 2, March 2002

• Peter Frankl, Vojtech Rödl: Extremal problems on set systems. 131-164
• Michal Parnas, Dana Ron: Testing the diameter of graphs. 165-183
• Michael A. Bender, Dana Ron: Testing properties of directed graphs: acyclicity and connectivity. 184-205
• Tao Jiang, Ming Li, Paul M. B. Vitányi: The average-case area of Heilbronn-type triangles. 206-219
• Matthias Löwe, Christian Meise: Right order spectral gap estimates for generating sets of Z₄. 220-238
• Aaron Abrams, Henry Landau, Zeph Landau, James Pommersheim, Eric Zaslow: Evasive random walks and the clairvoyant demon. 239-248
• Dimitris Achlioptas, Jeong Han Kim, Michael Krivelevich, Prasad Tetali: Two-coloring random hypergraphs. 249-259

Volume 20, Number 3, May 2002

• Tibor Jordán, Alessandro Panconesi:
  Preface. 261
  
• Van H. Vu:
  Concentration of non-Lipschitz functions and applications. 262-316
  
• Svante Janson, Andrzej Rucinski:
  The infamous upper tail. 317-342
  
• Robert D. Carr, Santosh Vempala:
  Randomized metarounding. 343-352
  
• Bernd Gärtner:
  The Random-Facet simplex algorithm on combinatorial cubes. 353-381
  
• Eran Halperin, Uri Zwick:
  A unified framework for obtaining improved approximation algorithms for maximum graph bisection problems. 382-402
  
• Uriel Feige, Gideon Schechtman:
  On the optimality of the random hyperplane rounding technique for MAX CUT. 403-440
  
• Claire Kenyon, Michael Mitzenmacher:
  Linear waste of best fit bin packing on skewed distributions. 441-464
  
• Goran Konjevod, R. Ravi, Aravind Srinivasan:
  Approximation algorithms for the covering Steiner problem. 465-482
  

Volume 20, Number 4, July 2002

• Gabriel Istrate:
  The phase transition in random horn satisfiability and its algorithmic implications. 483-506
  
• John C. Wierman:
  Bond percolation critical probability bounds for three Archimedean lattices. 507-518
  
• Remco van der Hofstad, Gerard Hooghiemstra, Piet Van Mieghem:
  On the covariance of the level sizes in random recursive trees. 519-539
  
• Nancy Garcia, José Luis Palacios:
  On mixing times for stratified walks on the d-cube. 540-552