Please join us on Friday, Jan 26, 2018 for our first annual Alumni Colloquium. Dr. Monika Heinig will give a talk entitled Cutting a Tree into a Forest: A Polynomial Time Algorithm & A Neurological Application at 13:15 in McNulty 107.
Dr. Heinig was a former student in our department and is giving the first talk in our new annual Alumni Colloquium.
About this talk: Graph theory is used in many industries as a way to describe and visualize data. Nodes can represent some feature(s) of the data (such as areas of the brain in neurology or stocks in financial engineering, for example) and weighted edges can correspond to some relationship between its endnodes. Such graphs tend to be very large and contain a lot of information, typically making computations difficult. As a way to ease computational complexity while retaining the characteristics of the original network, the graph can be reduced to a minimum or maximum spanning tree. From there, edges could be removed to yield a forest. To retain the most amount of information, we want to remove the minimum number of edges so that the sum of each of the edge weights in each surviving component is less than some predetermined threshold value k. In this talk, we present a polynomial time algorithm for reducing an edge weighted spanning tree to such a forest. We also present a direct application of the algorithm to functional MRI (fMRI) data as a means to study the neurological disease Multiple Sclerosis.