Random Structures and Algorithms, Volume 28

Volume 28, Number 1, January 2006

• Terence Tao, Van H. Vu:
  On random plus/minus 1 matrices: Singularity and determinant. 1-23
  
• Abraham D. Flaxman, Alan M. Frieze, Michael Krivelevich:
  On the random 2-stage minimum spanning tree. 24-36
  
• Heinrich Matzinger, Silke W. W. Rolles:
  Finding blocks and other patterns in a random coloring of Z. 37-75
  
• David Gamarnik, Tomasz Nowicki, Grzegorz Swirszcz:
  Maximum weight independent sets and matchings in sparse random graphs. Exact results using the local weak convergence method. 76-106
  
• Benjamin Doerr:
  Matrix rounding with respect to small submatrices. 107-112
  

Volume 28, Number 2, March 2006

• Brendan Nagle, Vojtech Rödl, Mathias Schacht:
  The counting lemma for regular k-uniform hypergraphs. 113-179
  
• Vojtech Rödl, Jozef Skokan:
  Applications of the regularity lemma for uniform hypergraphs. 180-194
  
• Tom Bohman, Jeong Han Kim:
  A phase transition for avoiding a giant component. 195-214
  
• Malwina J. Luczak, Tomasz Luczak:
  The phase transition in the cluster-scaled model of a random graph. 215-246
  

Volume 28, Number 3, May 2006

• Nicholas Pippenger, Kristin Schleich:
  Topological characteristics of random triangulated surfaces. 247-288
  
• Amin Coja-Oghlan, Cristopher Moore, Vishal Sanwalani:
  MAX k-CUT and approximating the chromatic number of random graphs. 289-322
  
• Alan M. Frieze, Michael Molloy:
  The satisfiability threshold for randomly generated binary constraint satisfaction problems. 323-339
  
• Stephan Mertens, Marc Mézard, Riccardo Zecchina:
  Threshold values of random K-SAT from the cavity method. 340-373
  
• Bernhard Gittenberger:
  Nodes of large degree in random trees and forests. 374-385
  

Volume 28, Number 4, July 2006

• Eli Ben-Sasson, Madhu Sudan:
  Robust locally testable codes and products of codes. 387-402
  
• Clément Dombry, Nadine Guillotin-Plantard, Bruno Pinçon, René Schott:
  Data structures with dynamical random transitions. 403-426
  
• David Galvin, Prasad Tetali:
  Slow mixing of Glauber dynamics for the hard-core model on regular bipartite graphs. 427-443
  
• Alexis C. Kaporis, Lefteris M. Kirousis, Efthimios G. Lalas:
  The probabilistic analysis of a greedy satisfiability algorithm. 444-480
  
• Tsung-Hsi Tsai:
  Average case analysis of the Boyer-Moore algorithm. 481-498
  
• Alan M. Frieze, Michael Krivelevich:
  Almost universal graphs. 499-510
  
• Svante Janson, Johan Wästlund:
  Addendum to "The Minimal Spanning Tree in a Complete Graph and a Functional Limit Theorem for Trees in a Random Graph". 511-512