You are here

Rutgers University, DIMACS

Title: Graph Theory, Algorithms, and Applications


Dates of Program: June 4 - July 27, 2012


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 (Wij = number of shared preys between ith and jth predators), is it possible to partition the competition graph G into two subgraphs GA and GB using a combination of Fiedler order and linkage-based 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 (Wij) 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

Michael Pearson
MAA Programs & Services