Global Sources
EE Times-India
Stay in touch with EE Times India
EE Times-India > Networks

Novel vertex connectivity improves network bandwidth

Posted: 30 Dec 2013     Print Version  Bookmark and Share

Keywords:MIT  network bandwidth  vertex connectivity  graph theory 

Researchers from MIT have unveiled a new approach to understanding a basic concept in graph theory, known as vertex connectivity, that could lead to communications protocols (rules that govern how digital messages are exchanged) that push as much bandwidth as possible from networks.

Graph theory plays a central role in mathematics and computer science, and is used to describe the relationship between different objects. Each graph consists of a number of nodes, or vertices, which represent the objects, and connecting lines between them, 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, 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.

In this way both concepts show how robust a network is against failure, and how much flow can pass through it, whether the flow of information in a communications network, traffic flow in a transportation system or fluid flow in hydraulics.

However, while a great deal of research has been carried out in mathematics to solve problems associated with edge connectivity, there has been relatively little success in answering questions about vertex connectivity.

But at the ACM-SIAM Symposium on Discrete Algorithms in Portland, Ore., 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.

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

In the 1960s, mathematicians William Tutte and Crispin Nash-Williams separately developed theories about structures called edge-disjoint spanning trees, which now serve as one of the key technical tools in many problems about edge connectivity.

1 • 2 Next Page Last Page

Comment on "Novel vertex connectivity improves n..."
*  You can enter [0] more charecters.
*Verify code:


Visit Asia Webinars to learn about the latest in technology and get practical design tips.


Go to top             Connect on Facebook      Follow us on Twitter      Follow us on Orkut

Back to Top