I am a mathematics major entering my senior year at Coe College in Cedar Rapids, IA. I am working with Professor Endre Boros of RUTCOR along with student Dan MacDonald of Seton Hall University on a problem in graph theory.
Our project explores how to generate short paths from initial vertex s to terminal vertex t with acceptable computational complexity. We are also considering minimal ways to cut those short paths.
Introduction to General Concepts:
A graph is any collection of vertices, or nodes, which are connected by edges. We say that G=(V,E), where G is the graph, V is the set of vertices, and E is the set of edges. Any path from a vertex s to another vertex t is short if its length is less than or equal to some threshold L. To cut those short paths, we choose a set of edges of the graph that we can delete in order to block all short paths from s to t. A cut is minimal if each of the edges in the cut-set is essential to block all short paths. In other words, if we were to take any of the edges out of the cut-set and reinsert it into the graph, then a short path would be possible.
You can see an example to illustrate these concepts here.
This problem has many applications to communications networks. For instance, telecommunications companies are interested in short paths because they are the most efficient and clear transmissions over a network. An understanding of how many cuts are possible in a network of short paths is important in estimating the reliabily of that network.
Approaching the Problem:
We approached this problem by looking at specific classes of graphs before generalizing to consider all graphs. One type of graph we studied is called a seesaw graph; it looks something like this. This graph is easy to work with because we can consider only the bottom line, directly from s to t or we can add in some or all of the "humps" above the line, depending on our L.
Another graph we considered is the hierarchical communications graph. It might look like this. This graph is interesting because it has applications to the real world of telecommunications networks. The structure of the graph boils down to two trees, each with c as its source, and the ends of trees are connected either to s or to t. Thus, depending on the algorithm, we could possibly consider each "side" of the graph separately.
You can see some of our formal results here. You can also view our final presentation, which we gave Wednesday, July 20th, here.