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
Electronic Edition (link) BibTeX
Robert B. Ellis, Xingde Jia, Catherine H. Yan:
On random points in the unit disk. 14-25
Electronic Edition (link) BibTeX
Zhicheng Gao, Daniel Panario:
Degree distribution of the greatest common divisor of polynomials over F_q. 26-37
Electronic Edition (link) BibTeX
Jean Bertoin, Grégory Miermont:
Asymptotics in Knuth's parking problem for caravans. 38-55
Electronic Edition (link) BibTeX
Elchanan Mossel, Amir Shpilka, Luca Trevisan:
On epsilon-biased generators in NC⁰. 56-81
Electronic Edition (link) BibTeX
Béla Csaba, Sachin Lodha:
A randomized on-line algorithm for the k-server problem on a line. 82-104
Electronic Edition (link) BibTeX
Mihyun Kang, Youngmee Koh, Sangwook Ree, Tomasz Luczak:
The connectivity threshold for the min-degree random graph process. 105-120
Electronic Edition (link) BibTeX

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

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

Jacob van den Berg, Olle Häggström, Jeff Kahn:
Some conditional correlation inequalities for percolation and related processes. 417-435
Electronic Edition (link) BibTeX
Michael Krivelevich, Asaf Nachmias:
Coloring complete bipartite graphs from random lists. 436-449
Electronic Edition (link) BibTeX
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
Electronic Edition (link) BibTeX
Johan Håstad:
The square lattice shuffle. 466-474
Electronic Edition (link) BibTeX
Mireille Bousquet-Mélou:
Limit laws for embedded trees: Applications to the integrated superBrownian excursion. 475-523
Electronic Edition (link) BibTeX
Béla Bollobás, Oliver Riordan:
Sharp thresholds and percolation in the plane. 524-548
Electronic Edition (link) BibTeX
Colin McDiarmid, Bruce A. Reed:
Concentration for self-bounding functions and an inequality of Talagrand. 549-557
Electronic Edition (link) BibTeX