Computer Scientists Uncover New Approach to Maximize Networks' Bandwidth

Computer scientists are constantly searching for ways to squeeze more and more bandwidth from communications networks. Now, they may have succeeded. They've found a new approach to understanding a basic concept in graph theory that could ultimately coax as much bandwidth as possible from networks.

Graph theory plays a central role in mathematics and computer science. It's used to describe the relationship between different objects. Each graph consists of a number of nodes, or vertices, which represent the objects. They also consist of connecting lines between them, which are known as edges, which signify the relationships between them. 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. This 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, the easier it is to break apart. This shows how robust a network is against failure and how much flow can pass through it.

While there's been quite a few studies about edge connectivity, though, there's been relatively little success in answering questions about vertex connectivity. That's why researchers took a closer look.

They created an analogous theory about vertex connectivity. The researchers broke 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 the ones inside the group. In this way, information can be disseminated among the nodes of the set and passed to any other node in the network.

"So if you think of an application like broadcasting information through a network, we can now decompose the network into many groups, each being one connected dominating set," said Mohsen Ghaffari, one of the researchers, in a news release. "Each of these groups is then going to be responsible for broadcasting some set of the messages, and all groups work in parallel to broadcast all the messages fast-almost as fast as possible."

The findings could be used to analyze the robustness of a network against random failures. In addition, the new techniques could allow them to analyze whether a network is likely to remain connected when its nodes fail randomly with some given problem.