2 papers
cs.DS2019
Distributed MST: A Smoothed Analysis
Soumyottam Chatterjee, Gopal Pandurangan, Nguyen Dinh Pham
We study smoothed analysis of distributed graph algorithms, focusing on the fundamental minimum spanning tree (MST) problem. With the goal of studying the time complexity of distri…
cs.DS2018
Fast and Efficient Distributed Computation of Hamiltonian Cycles in Random Graphs
Soumyottam Chatterjee, Reza Fathi, Gopal Pandurangan +1
We present fast and efficient randomized distributed algorithms to find Hamiltonian cycles in random graphs. In particular, we present a randomized distributed algorithm for the $G…