David R. Morrison

Harvey Mudd College Mathematics 2008

Thesis Proposal: Edge Control Sets
Joint Meetings Poster: AMS/MAA Undergraduate Poster Session
Thesis: Thesis (18 April 2008)
HMC Presentation Days Poster: HMC Presentation Days Poster Session
HMC Presentation Days Slides: HMC Thesis Final Presentation

Thesis Advisor: Prof. Susan Martonosi
Second Reader: Dr. Kimberly Tucker

Characteristics of Optimal Solutions to the Sensor Location Problem

Congestion and over-saturated roads pose significant problems and create delays in every major city in the world. Before this problem can be addressed, we must know how much traffic is flowing over the links in the network. We transform a road network into a directed graph with a network flow function, and ask the question, ``What subset of vertices (intersections) should be monitored such that knowledge of the flow passing through these vertices is sufficient to calculate the flow everywhere in the graph?'' To minimize the cost of placing sensors, we seek the smallest number of monitored vertices. This is known as the Sensor Location Problem (SLP). We explore conditions under which a set of monitored vertices produces a unique solution to the problem and disprove a previous result published on the problem. Finally, we explore a matrix formulation of the problem and present cases when the flow can or cannot be calculated on the graph.


Annotated Bibliography (Updated 26 Sept. 2007)