New breakthrough could help maximize bandwidth from communications networks

A new approach to understanding a basic concept in graph theory, known as "vertex connectivity," could lead to communications protocols - the rules that govern how digital messages are exchanged - that coax as much bandwidth as possible from networks, researchers have claimed.

A communications network, for example, can be represented as a graph with each node in the network being one vertex, and a connection between two nodes depicted as an edge.

One of the fundamental concepts within graph theory is connectivity, which has two variants: edge connectivity and vertex connectivity. These are numbers that determine how many lines or nodes would have to be removed from a given graph to disconnect it.

The lower the edge-connectivity or vertex-connectivity number of a graph, therefore, the easier it is to disconnect, or break apart.

At the ACM-SIAM Symposium on Discrete Algorithms in Portland, Oregon, in January, Mohsen Ghaffari, a graduate student in the Computer Science and Artificial Intelligence Laboratory at MIT, will present a new technique for addressing vertex-connectivity problems.

Ghaffari, who developed the new approach alongside Keren Censor-Hillel at the Technion and Fabian Kuhn at the University of Freiburg, said that this could ultimately help them understand how to build more robust and faster networks.

The team has created an analogous theory about vertex connectivity. They did this by breaking down the graph into separated groups of nodes, known as connected dominating sets. In graph theory, a group of nodes is called a connected dominating set if all of the vertices within it are connected to one another, and any other node within the graph is adjacent to at least one of those inside the group.

The team developed an algorithm that can carefully decompose a network into many connected dominating sets. In this way, it can structure so-called wireless ad hoc networks, in which individual nodes route data by passing it from one to the next to ensure the best possible speed of information flow.