Random Structures and Algorithms, Volume 29

Volume 29, Number 1, August 2006

• Béla Bollobás, Jeong Han Kim, Jacques Verstraëte:
  Regular subgraphs of random graphs. 1-13
  
• Robert B. Ellis, Xingde Jia, Catherine H. Yan:
  On random points in the unit disk. 14-25
  
• Zhicheng Gao, Daniel Panario:
  Degree distribution of the greatest common divisor of polynomials over F_q. 26-37
  
• Jean Bertoin, Grégory Miermont:
  Asymptotics in Knuth's parking problem for caravans. 38-55
  
• Elchanan Mossel, Amir Shpilka, Luca Trevisan:
  On epsilon-biased generators in NC⁰. 56-81
  
• Béla Csaba, Sachin Lodha:
  A randomized on-line algorithm for the k-server problem on a line. 82-104
  
• Mihyun Kang, Youngmee Koh, Sangwook Ree, Tomasz Luczak:
  The connectivity threshold for the min-degree random graph process. 105-120
  

Volume 29, Number 2, September 2006

• Andreas Maurer:
  Concentration inequalities for functions of independent variables. 121-138
  
• Svante Janson:
  Random cutting and records in deterministic and random trees. 139-179
  
• Michael Krivelevich, Benny Sudakov, Prasad Tetali:
  On smoothed analysis in dense graphs and formulas. 180-193
  
• Zsolt Katona:
  Levels of a scale-free tree. 194-207
  
• Yotam Drier, Nathan Linial:
  Minors in lifts of graphs. 208-225
  
• Jonathan Jordan:
  The degree sequences and spectra of scale-free random graphs. 226-242
  
• Shuji Kijima, Tomomi Matsui:
  Polynomial time perfect sampling algorithm for two-rowed contingency tables. 243-256
  

Volume 29, Number 3, October 2006

• Michel X. Goemans, Jan Vondrák:
  Covering minimum spanning trees of random subgraphs. 257-276
  
• Ross G. Pinsky:
  Law of large numbers for increasing subsequences of random permutations. 277-295
  
• Toyoaki Sugimoto, Naoto Miyoshi:
  On the asymptotics of fault probability in least-recently-used caching with Zipf-type request distribution. 296-323
  
• Noga Alon, Eitan Bachmat:
  Regular graphs whose subgraphs tend to be acyclic. 324-337
  
• Matthias Heveling, Günter Last:
  Existence, uniqueness, and algorithmic computation of general lilypond systems. 338-350
  
• Amin Coja-Oghlan:
  A spectral heuristic for bisecting random graphs. 351-398
  
• Paul N. Balister, Béla Bollobás, Robert Kozma:
  Large deviations for mean field models of probabilistic cellular automata. 399-415
  

Volume 29, Number 4, December 2006

• Jacob van den Berg, Olle Häggström, Jeff Kahn:
  Some conditional correlation inequalities for percolation and related processes. 417-435
  
• Michael Krivelevich, Asaf Nachmias:
  Coloring complete bipartite graphs from random lists. 436-449
  
• Martin E. Dyer, Abraham D. Flaxman, Alan M. Frieze, Eric Vigoda:
  Randomly coloring sparse random graphs with fewer colors than the maximum degree. 450-465
  
• Johan Håstad:
  The square lattice shuffle. 466-474
  
• Mireille Bousquet-Mélou:
  Limit laws for embedded trees: Applications to the integrated superBrownian excursion. 475-523
  
• Béla Bollobás, Oliver Riordan:
  Sharp thresholds and percolation in the plane. 524-548
  
• Colin McDiarmid, Bruce A. Reed:
  Concentration for self-bounding functions and an inequality of Talagrand. 549-557