Fabian Kuhn
ABSTRACT
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?
Index Terms
- A distributed perspective on graph connectivity and cuts
Recommendations
The connectivity and the Harary index of a graph
The Harary index of a graph is defined as the sum of reciprocals of distances between all pairs of vertices of the graph. In this paper we provide an upper bound of the Harary index in terms of the vertex or edge connectivity of a graph. We characterize ...
A representation of cuts within 6/5 times the edge connectivity with applications
FOCS '95: Proceedings of the 36th Annual Symposium on Foundations of Computer ScienceLet G be an undirected c-edge connected graph. In this paper we give an O(n/sup 2/)-sized planar geometric representation for all edge cuts with capacity less than 6/5c. The representation can be very efficiently built, by using a single run of the ...
On the sum of all distances in bipartite graphs
The transmission of a connected graph G is the sum of all distances between all pairs of vertices in G, it is also called the Wiener index of G. In this paper, sharp bounds on the transmission are determined for several classes of connected bipartite ...
Comments