Title: Graph Theory, Algorithms, and Applications
Directors:
Dates of Program: June 4  July 27, 2012
Summary:
Participants will be using graph theoretic approaches to study pollution control. In pollution control, students will develop graph theoretic algorithms to analyze pollution effects to determine the least polluted path. This problem focuses on choosing the "least polluting" path when driving from a given starting position A to a given arrival position B. Students will use data available on the web to develop graph theoretic algorithms to estimate the pollution effect, and thus determine an optimal path. Cluster analysis in graph theory is a popular method to seek partition of a given data set into several clusters so that the data points within the same cluster are more similar than those belonged in the separate clusters. In biodiversity project students will seek answer to the following question: Given the competition graph G = (V,E) (based on Hudson River data sets) with the node set (species) V, edge set E, and the weight matrix W (W_{ij} = number of shared preys between i^{th} and j^{th} predators), is it possible to partition the competition graph G into two subgraphs G_{A} and G_{B} using a combination of Fiedler order and linkagebased refinements [Ding, C. HQ et al.] to minimize cut(A,B) while maximizing W(A) and W(B) at the same time. The strength between two nodes (species) is given by their edge weight (W_{ij}) and the strength between two clusters A and B is given by
Besides providing analytical and numerical presentations, students will also participate in all DIMACS activities including workshops, seminars, and presentations and will deliver written reports.
Student Researchers Supported by MAA:

Fredric Anglade

Daniel Brown

Paul Cabrera

Alassane Ngaide
Program Contacts:
Bill Hawkins
MAA SUMMA
bhawkins@maa.org
2023198473
Michael Pearson
MAA Programs & Services
pearson@maa.org
2023198470