# Efficient Distributed Algorithms on Random Graphs

## Date

## Authors

## Journal Title

## Journal ISSN

## Volume Title

## Publisher

## Abstract

This dissertation focuses on two prominent graph problems: finding Hamiltonian cycles and detecting communities in graphs. Both of them are NP-hard problems on general graphs but can admit efficient solutions in {\em random graphs}. In this dissertation, we present efficient distributed algorithms for the above two problems in random graphs. First, we present fast and efficient randomized distributed algorithms to find Hamiltonian cycles in random graphs. In particular, we design and analyze a randomized distributed algorithm for the classical