Maximizing Network Bandwidth with New Graph Theory ConceptCategory: Science & Technology
Posted: January 9, 2014 01:23PM
Graph theory is a valuable tool in mathematics and computer science as it allows one to analyze and study how objects are connected. It should not be surprising then that it is especially important for developing computer networks. Researchers at MIT have recently developed a new concept which could lead to computer networks running at almost theoretical maximums.
Graphs are made up of vertices and the edges that connect them, and both edge-connectivity and vertex-connectivity indicate how easily a graph can be disconnected. In the sixties researchers were able to relate edge-connectivity to edge-disjoint spanning trees, which are independent paths between vertices. With multiple spanning trees, if one path is lost, information can flow along the other(s). What the MIT researchers have done is related vertex-connectivity to connected dominating sets, which are the vertex-based equivalent to the spanning trees. Within a connected dominating set, every vertex is connected to each other, or is adjacent to one that is.
While edge-disjoint spanning trees will make a network less likely to fail, vertex disjoint connected dominating sets will allow information to be spread faster along a network. The network can be broken into groups and the information broadcasted in parallel through it, almost as quickly as is possible.