| Random graphs have an important role to play in modeling complex networks and their behavior and in studying the performance of network algorithms. In this thesis, we begin by studying the Hamiltonicity property of the Random lift model introduced by Linial et al. in both undirected and directed settings. Next, we analyze the Random-Surfer Web-Graph model introduced by Blum et al. Finally, we study the performance of two matching algorithms - a linear expected time matching algorithm for sparse random graphs and a greedy matching algorithm for sparse random uniform hypergraphs. |
