Random Structures and Algorithms, Volume 16

Volume 16, Number 1, January 2000

• Michal Karonski, Joel Spencer:
  Ten Years! 1-3
  
• Jaikumar Radhakrishnan, Aravind Srinivasan:
  Improved bounds and algorithms for hypergraph 2-coloring. 4-32
  
• Colin Cooper, Alan M. Frieze, Kurt Mehlhorn, Volker Priebe:
  Average-case complexity of shortest-paths problems in the vertex-potential model. 33-46
  
• Zhicheng Gao, Brendan D. McKay, Xiaoji Wang:
  Asymptotic enumeration of tournaments with a given score sequence containing a specified digraph. 47-57
  
• Peter Winkler:
  Dependent percolation and colliding random walks. 58-84
  
• David Bruce Wilson: How to couple from the past using a read-once source of randomness. 85-113

Volume 16, Number 2, March 2000

• Johan Jonasson:
  Lollipop graphs are extremal for commute times. 131-142
  
• Christopher Hoffman:
  Energy of flows on Z2 percolation clusters. 143-155
  
• James Allen Fill, Edward R. Scheinerman, Karen B. Singer-Cohen:
  Random intersection graphs when m=omega(n): An equivalence theorem relating the evolution of the G(n, m, p) and G(n, p) models. 156-176
  
• Yoshiharu Kohayakawa, Bernd Kreuter, Deryk Osthus:
  The length of random subsets of Boolean lattices. 177-194
  
• Uriel Feige, Robert Krauthgamer:
  Finding and certifying a large hidden clique in a semirandom graph. 195-208
  
• Colin Cooper:
  On the rank of random matrices. 209-232
  

Volume 16, Number 3, May 2000

• Petr Savický:
  On random orderings of variables for parity ordered binary decision diagrams. 233-239
  
• Susanne Albers, Michael Mitzenmacher:
  Average-case analyses of first fit and random fit bin packing. 240-259
  
• Tomasz Luczak:
  On triangle-free random graphs. 260-276
  
• Stéphane Boucheron, Gábor Lugosi, Pascal Massart:
  A sharp concentration inequality with applications. 277-292
  

Volume 16, Number 4, July 2000

• Claudia Bertram-Kretzberg, Hanno Lefmann:
  MOD_p-tests, almost independence and small probability spaces. 293-313
  
• Wenceslas Fernandez de la Vega, Marek Karpinski:
  Polynomial time approximation of dense weighted instances of MAX-CUT. 314-332
  
• Johan Jonasson, Elchanan Mossel, Yuval Peres:
  Percolation in a dependent random environment. 333-343
  
• Van H. Vu:
  On the concentration of multivariate polynomials with small expectation. 344-363
  
• Noga Alon:
  Degrees and choice numbers. 364-368
  
• Colin Cooper, Alan M. Frieze:
  Hamilton cycles in random graphs and directed graphs. 369-401
  

Last update Sat May 18 17:13:12 2013 CET by the DBLP Team — Data released under the ODC-BY 1.0 license — See also our legal information page