A distributed perspective on graph connectivity and cuts
Fabian Kühn · 2014
Edge and vertex connectivity, as well as edge and vertex cuts are among the most basic and fundamental concepts in graph theory. In particular, they are naturally significant in a networking context as they are a measure for the rate at which information can be transferred across a network. While in a traditional, sequential setting, there is a rich literature (in particular on problems related to edge connectivity and edge cuts), until recently, much less was known from a distributed algorithms point of view. In my talk, I will discuss and give partial answers to some of the following basic questions. Using distributed algorithms, how fast can we compute or approximate the edge or vertex connectivity and is it possible to efficiently find small cuts in a network? Assuming, we have a network with good connectivity properties, to what extent is it possible to exploit this in order to speed up distributed computations? Where such properties can be exploited, are there network structures that allow to make use of good connectivity in a structured (and somewhat canonical) way and can we construct such structures in a distributed manner?