Communications of the ACM
New Approach to Vertex Connectivity Could Maximize Networks' Bandwidth
A new technique for addressing vertex-connectivity problems could result in faster, more robust networks.
Credit: MIT News
One of the fundamental concepts within graph theory is connectivity, in which edge connectivity and vertex connectivity act as variants. Although there has been a substantial amount of research focused on solving problems associated with edge connectivity, there has been very little success in answering questions surrounding vertex connectivity. However, researchers at the Massachusetts Institute of Technology (MIT), Technion, and the University of Freiburg say they have developed a technique for addressing vertex-connectivity problems.
"This could ultimately help us understand how to build more robust and faster networks," says MIT graduate student Mohsen Ghaffari, who will present the research at the ACM-SIAM Symposium on Discrete Algorithms in Portland, OR, in January.
The technique involves breaking down the graph into separated groups of nodes, called connected domain sets. "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," Ghaffari says.
The researchers also have developed an algorithm that can carefully decompose a network into many connected dominating sets. "We want to be able to spread as much information as possible per unit of time, to create faster and faster networks, and when a graph has a better vertex connectivity, it allows a larger flow [of information]," Ghaffari says.
From MIT News
View Full Article
Abstracts Copyright © 2013 Information Inc., Bethesda, Maryland, USA
No entries found