Session 14

9:00-9:20 RNC Algorithms for the Uniform Generation of Combinatorial Structures

Michele Zito, Ida Pu, Martyn Amos, and Alan Gibbons, University of Warwick, United Kingdom

9:25-9:45 Optimal Randomized EREW PRAM Algorithms for Finding Spanning Forests and for Other Basic Graph Connectivity Problems

Shay Halperin and Uri Zwick, Tel-Aviv University, Israel

9:50-10:10 How to Get an Exact Sample From a Generic Markov Chain and Sample a Random Spanning Tree from a Directed Graph, Both Within the Cover Time

David Bruce Wilson and James Gary Propp, Massachusetts Institute of Technology

10:15-10:35 Error-Resilient DNA Computation

Richard M. Karp, University of California, Berkeley and International Computer Science Institute; Claire Kenyon, CNRS, Ecole Normale Superieure de Lyon, France; and Orli Waarts, University of California, Berkeley

Registration | Hotel Information | Transportation | Author Index