67 citations · 140 across the 37 of their papers we have counts for
8 papers · 1 filter
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…
Time-Message Trade-Offs in Distributed Algorithms
Robert Gmyr, Gopal Pandurangan
This paper focuses on showing time-message trade-offs in distributed algorithms for fundamental problems such as leader election, broadcast, spanning tree (ST), minimum spanning tr…
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…
Sublinear Bounds for Randomized Leader Election
Shay Kutten, Gopal Pandurangan, David Peleg +2
This paper concerns {\em randomized} leader election in synchronous distributed networks. A distributed leader election algorithm is presented for complete -node networks that r…
Efficient Computation of Distance Sketches in Distributed Networks
Atish Das Sarma, Michael Dinitz, Gopal Pandurangan
Distance computation is one of the most fundamental primitives used in communication networks. The cost of effectively and accurately computing pairwise network distances can becom…
Distributed Agreement in Dynamic Peer-to-Peer Networks
John Augustine, Gopal Pandurangan, Peter Robinson +1
Motivated by the need for robust and fast distributed computation in highly dynamic Peer-to-Peer (P2P) networks, we study algorithms for the fundamental distributed agreement probl…