Graduation Year
2008
Document Type
Open Access Senior Thesis
Degree Name
Bachelor of Science
Department
Mathematics
Reader 1
Susan E. Martonosi
Reader 2
Kimberly Tucker
Abstract
Congestion and oversaturated 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.
Recommended Citation
Morrison, David, "Characteristics of Optimal Solutions to the Sensor Location Problem" (2008). HMC Senior Theses. 210.
https://scholarship.claremont.edu/hmc_theses/210
