BARC talk by Valerie King

Thursday, November 29th, Valerie King, Professor at Department of Computer Science, University of Victoria, Canada, will give a talk in BARC "Constructing a minimum spanning tree with sublinear communication in a distributed network"

Title

Constructing a minimum spanning tree with sublinear communication in a distributed network

Abstract

How can a minimum spanning tree or even any spanning tree be constructed in a distributed network using communication sublinear in the number of edges?   Here we assume each node only knows its neighbors and communication is by message-passing.  I'll  show that this can be done (for dense networks) even in an asynchronous network.

Read more about Valerie King.