## Project Description:s to terminal vertex t with acceptable computational complexity. We are also considering minimal ways to cut those short paths.
## Introduction to General Concepts: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.
## Applications:
## Approaching the Problem: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 You can see some of our formal results here. You can also view our final presentation, which we gave Wednesday, July 20th, here. |