Evacuating graphs Graph g=(V, E) represents structure Vertices are rooms, Edges are hallways Vertices are Buildings, Edges are roads Edge weight Te is transit time on edge Edge capacity Ce is " width Special vertices(sinks)are emergency exits In case of emergency, want to evacuate everybody to exits as quickly as possible Problem: Design good Evacuation Protocols Often Approached via Dynamic Flow NetworksEvacuating Graphs • Graph G=(V,E) represents structure • Vertices are rooms, Edges are Hallways • Vertices are Buildings, Edges are roads • Edge weight 𝜏e is transit time on edge • Edge capacity ce is “width” • Special vertices (sinks) are emergency exits • In case of emergency, want to evacuate everybody to exits as quickly as possible • Problem: Design Good Evacuation Protocols • Often Approached via Dynamic Flow Networks