Skip Navigation

Scholars Day 2005, Wednesday, April 13

Routing Using Minimum Connected Dominating Sets

Currently available routing algorithms are not able to keep up with the growth in computer networks and calls for a new approach. In the past we had simple static networks and routing between two nodes used the simple application of graph theory. However, with the advent of mobile computing and the increasing need to traverse between larger distances, computer networks have become dynamic. We have avoided dynamic networks as a base model to create routing algorithms since most of the algorithms for dynamic graphs belong to NP-hard and NP-complete class of algorithm complexity. But now we require a framework to study dynamic networks and the new class of graph theory problems in Wireless Networks. We hypothesize that every dynamic computer network can be modeled from a base static network. Further we propose that although a lot of the current solutions are in the NP class of problems, with heuristic and probabilistic approximation we can adopt algorithms while keeping their complexity in the P class. A key component of this framework is the concept of “Minimum Connected Dominating Sets” which is defined as a set of vertices from which all other vertices in the graph are one edge away. This however is a NP hard problem which is being used in the current research to solve problems in routing and network-construction using heuristics algorithms.

Presenter: Srinivas Krishnan (Undergraduate Student)
Topic: Computer Science
Location: 104 Edwards
Time: 3:10 pm (Session IV)