Filed under: Uncategorized | Tags: distributed computing, students, theory
This is a neat result in the dynamic graph setting where an adversary can add and delete edges in a graph, but the number of nodes is always fixed at n. One of their results is as follows. In the case where the maximum number of rounds that it takes a message to traverse the network is always polylog, they give a polylog time algorithm that allows each node to approximate within a constant factor the densest subgraph. This is in the CONGEST model where in each round, each node can send an O(log n) bit message to each neighbor.
Leave a Comment so far
Leave a comment