Kistine Andall's REU 2013 Web Page

About Me

Name: Kistine Andall
Email: kistineandall(at) dimax.rutgers.edu
Office: 442 CoRE Building
Home Institution: Howard University
Project: Greenest Path

About My Project

Mathematics of Planet Earth represents the aim of many worldwide Mathematics organisations to find mathematical solutions to Earth's problems. This project is an extension of this initiative in conjunction with the DIMACS department of Rutgers University. There has been an increase in the severity and frequency of natural disasters and the need for rapid emergency response has been recently highlighted. The redistribution of resources in the aftermath of these disasters is often critical to the survival and health of those affected. The Greenest Path project is directed at finding ways to make this process as efficient as possible.

The aim of this project is to find the optimum pathway to transport resources between points during an emergency. Graph pebbling, which is a subset of graph theory is being investigated as the primary method of modelling the pathways and establishing the best one. Pebbling is based on the notion that at least one pebble must be sacrificed to move another pebble from one point on a graph to the other along an edge. The pebbles represent resources in this case and our hope is to use this field to create an algorithm that can optimizet the distribution of these resources.

Progress Report

Week 1

The focus has been on understanding the fundamentals of Graph Theory and pebbling. Several papers have been published on the topic and a literature rveiew is being conducted to isolate the information most relevant to the project. A poster summarizing the goals of our project as well as the projected path our research will take was presented. A group presentation consisting of Adam Ibrahim, Alan Jara and myself was also given to our fellow researchers and mentors at DIMACS

Week 2

Various papers pertaining to the topic were read. Some of particular interest are: Optimal pebbling of graphs by Jessica Muntza, Sivaram Narayana, Noah Streib, and Kelly Van Ochten. General graph pebbling by Glenn Hurlbert, which provides a great introduction to the concept of graph pebbling and A Graph Pebbling Algorithm on Weighted Graphs by Nandor Sieben. Sieben developed an algorithm which found the pebbling number of graphs. His methodolgy could be beneficial to our research.

Week 3

After doing extensive reading, some of the equations given in the papers were proved. My fellow researchers and I also explored the option of making modifications to existing theories or graphs to customize them to our purpose.

Week 4

Dijkstra's Algorithm was analyzed as an algorithm that can be utilized It performs an exhaustive search that guarantees the shortest pathway. It may be inefficient for large searches however. The following is an example of how the algorithm processes distances. I used a problem that can be found on page 76 of Introduction to Graph Theory by Douglas B. West

.

Weeks 5 and 6

I spent these two weeks trying to figure out if there was a way to get the accuracy of Dijkstra's algorithm without using an exhaustive search. The answer so far is no. I tried to think of various ways to do the algorithm and will attempt to find the Order of the algorithm to determine how efficient it is compared to other alternatives. I'll be doing some reading on big-O notation and will update my progress next week

Here is my mentor's website and the REU website: