Name: | Adam Ibrahim |
---|---|
Email: | ibrahimadam193 (at) gmail.com |
Office: | CoRE 431 (I'm rarely ever there.) |
Home Institution: | New York City College of Technology |
Project: | Applying Graph Pebbling to Resource Allocation During Extreme Events |
My project centers around the area of study in Graph Theory called Graph Pebbling. This consists of placing an arbitrary, nonnegative amount of pebbles at each vertex in a graph. These pebbles are supposed to model some sort of resource. If you want to move a pebble from a vertex u to an adjacent vertex v , you would have to discard a pebble from u beforehand, then take an additional pebble from u and move it to v . The amount of pebbles that are discarded can be changed. This is intended to model the consupmtion of resources in moving around materials. Since there is no difference from pebble to pebble, they all represent the same resource. An example of something this could model is transporting tanks of gas by using trucks. The trucks have to use gas to transport gas containers, so the discarded pebbles are consumed gas and the moved pebble is transported gas.
This week was my introduction to the program. I got settled in, learned the lay of the land and was introduced to the faculty. As a group, my partners and I also constructed a poster for a sustainability conference to talk about the goal of our work.
During this week, we began a literature review in earnest, so that we could prepare ourselves for the research ahead. We consulted resources on Graph Theory and Graph Pebbling, familiarizing ourselves with some basic concepts so that we could start diving into the research as soon as possible. I think we're ready to do this during the next week. We paid particular attention to weighted graphs and papers describing algorithms for finding the pebbling number of a graph.
As a group, we're beginning to test out the waters of mathematical research. We're still learning pebbling concepts and Graph Theory concepts, but we've started to make approaches to our problem, considering algorithms for finding the shortest path in a weighted or unweighted graph, as well as studying how to modify these algorithms for use in Graph Pebbling.
Our work in exploring the algorithms may have paid off. Specifically, we looked at Dijkstra's Algorithm for finding the shortest path in a weighted graph, since we will most often be working with weighted graphs. We dissected it and modified the algorithm to find the paths between vertices that require the fewest amount of pebbles on one endpoint to move a pebble to the other endpoint. This will help us find efficient routes for transporting resources.
We're finalizing our work with Dijkstra's Algorithm, making final checks on what was done in trying to utilize the algorithm. If everything checks out, we may program the new algorithm. We're exploring representing weighted graphs and pebbling configurations together within a matrix. This will help us in programming algorithms that deal with pebbling graphs and representing the graph as a matrix could possibly shed some insight on new things in pebbling using results that have been proven for matrices.
Urmi Ghosh-Dastidar