Random Graphs and Algorithms
In order to distinguish essays and pre-prints from academic theses, we have a separate category. These are often much longer text based documents than a paper.
This thesis is concerned with the study of random graphs and random algorithms. There are three overarching themes. One theme is sparse random graphs, i.e. random graphs in which the average degree is bounded with high probability. A second theme is that of finding spanning subsets such as spanning trees, perfect matchings and Hamilton cycles. A third theme is solving optimization problems on graphs with random edge costs.