Machinations


Dense Subgraphs on Dynamic Networks
November 5, 2012, 10:17 pm
Filed under: Uncategorized | Tags: , ,

A quick pointer to an interview with my former student Amitabh Trehan on his DISC paper “Dense Subgraphs on Dynamic Networks” .

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.

Advertisements

Leave a Comment so far
Leave a comment



Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s



%d bloggers like this: