You are here

Rutgers University

Title: Sustainability and Graph Theory

Directors: Eugene Fiorini, Urmi Ghosh-Dastidar


Dates of Program: July 1 - August 16, 2013


This project explored the core concepts of graph theory, algorithms, and their applications to sustainability involved in finding a cost effective or energy efficient path while moving from vertex v to another distinct vertex u, and analyzed connectivity patterns of a network (resource allocation) that changes over time and then developed an optimal resource allocation distribution algorithm. Students from San Diego City College and New York City College of Technology formed research teams, joined by two additional students participating in the DIMACS REU program, to work on each problem.

Available data on the web was used to develop a graph theoretic algorithm to estimate the energy efficient path, and thus determine an optimal path. One student team focused on finding efficient paths for moving resources. The most efficient paths minimize the total cost of resources to a network. Specifically, when a witness is applied to a graph that moves resources along a path, an efficient pebbling path will minimize. The weight of a path is related to the cost of the witness that moves a pebble from one endpoint of a path to the other endpoint of a path.

The second student team identified similarities between the bicycle reallocation problem and the firefighter resource location problem proposed by Hartnell [1995]. Using algorithmic graph theory techniques, the second student team developed an algorithm that reallocated (firefighter) resources to areas in need of those resources, using real data from San Deigo County records to test their algorithm.

Students were introduced to industrial research by making a trip to a well-known DIMACS’ partner industry or research institute: AT&T Research Labs. The students were given a tour of the facilities and attended several technical presentations. Just as it is important for the students to be exposed to a global academic Rutgers University environment, students are served well by the opportunity to explore different corporate or applied research environments. Besides REU activities, students were encouraged to take advantage of all of the DIMACS activities including the many on-going seminars and workshops.

Student Researchers Supported by MAA:

Sergio Alphonso Sandoval Escobedo
Adam Ibrahim
Alan Jara
Leonard Lopez

Student Researchers Supported by Other Programs:
          Paul Alvarez, Rutgers University
          Kistine Andall, Howard University

Program Contacts:

Bill Hawkins

Support for NREUP is provided by the National Science Foundation's Division of Mathematical Sciences and the National Security Agency.