Fast and Efficient Distributed Computation of Hamiltonian Cycles in Random Graphs

04/24/2018
by   Soumyottam Chatterjee, et al.
0

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(n,p) random graph model, with number of nodes n and p=c n/n^δ (for any constant 0 < δ≤ 1 and for a suitably large constant c > 0), that finds a Hamiltonian cycle with high probability in Õ(n^δ) rounds (the notation Õ hides a polylog(n) factor). Our algorithm works in the (synchronous) CONGEST model (i.e., only O( n)-sized messages are communicated per edge per round) and its computational cost per node is sublinear (in n) per round and is fully-distributed (each node uses only o(n) memory and all nodes' computations are essentially balanced). Our algorithm improves over the previous best known result in terms of both the running time as well as the edge sparsity of the graphs where it can succeed; in particular, the denser the random graph, the smaller is the running time.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset