DIMACS
DIMACS REU 2013

General Information

me
Student: Leonard Lopez
Office: CoRE 434
School: San Diego City College
E-mail: lopez.leonardg@gmail.com
Project: Applying Line Graphs to Resource Allocation During Extreme Eevents
 Project Poster

Project Description

Over the past half century the magnitude and cost of natural disasters has generally increased in the United States. As the number of these natural disasters continues to rise, it has become imperative to develop a system that efficiently allocates resources to affected areas and effectively distributes services during the emergency event. Using a Bike Sharing System as a model, our objective is to use line graphs combined with principles of graph theory to develop a solution capable of optimizing resource allocation during an emergency event.


Weekly Log

Week 1:
Monday was orientation day, where I was able to meet faculty and other REU students. After orientation I met with my mentor, Dr. Gene Fiorini, and partner, Sergio Sandoval, to discuss and plan our project. On wednesday I attended the DIMACS/CCICADA Workshop on S&T Innovations in Hurricane Sandy Research where I was able to take note of several sustainability projects. At the workshop I also presented a poster that outlined goals and expectations for the project. A presentation about our project was given on Friday morning.
Week 2:
This week I began doing a literature review on line graphs, interval graphs, time graphs, and their applications. Upon meeting with my mentor we decided to narrow our project to focus on resource allocation during wildfires. On Wednesday I attended the CCICADA weekly CRG Lab Meeting and took notes on current projects related and applicable to my own project. As the week progressed I began to review algorithms that model fire spreading and I began collecting historical data on wildfires in the Southern California region.
Week 3:
This week I continued my research on fire spreading and collected climate data on Southerm California using the National Oceanic and Atmospheric Administration (NOAA) database. Upon attending the CCICADA CRG Lab Meeting this week, I was referred to several different articles related to my project.
Week 4:
I continued to research fire spreading models and began to work on an open problem that involves viewing the firefighter problem from the perspective of a weighted graph. I also gave a presentation during culture day about the culture of the MESA Program.
Week 5:
To develop an applicable approach, I've started modeling the region of Southern California as a graph. I've also began to compile all the data I've collected so far to add weights to the graph. On the mathematical approach I'm reviewing Paul Raff 's approach on the general firefighter problem on ZxZ and trying to adapt the problem by using weights.
Week 6:
We've adapted the general firefighter problem by adding directions to each edge. Upon reviewing different instances of the grid, we're working on an alogirthm that centers around focusing the fire into sink nodes. The ideas we are currently pursuing to establish the algorithm include finding the shortest path to each sink node and minmizing the amount of susceptible vertices after every turn.
Week 7:
This week I've continued my work on progressing the algorithm and I'm working on a Maple program that will randomly generate an n x n directed grid. The program will help me test the algorithm on larger grids. I'm also preparing a PowerPoint for the final presentations that will be given on Friday.
Week 8:
We've begun to examine in more detail some special cases of infinite directed grids. Using the algorithms we develop to solve the special cases, we plan to further develop our current strategy to solve our approach of the firefighter problem. I am compiling a final report of our progress to be turned in to DIMACS.

Presentations


Additional Information