Efficient Recomputations for Changeful Problems

Efficient Recomputations for Changeful Problems
Graph algorithms are used to efficiently compute answers to questions about graphs and networks. When the graph or network is prone to changes, a new task arises: that of adjusting the answer to fit the new instance after each change. In this project, we will develop new algorithms with strong theoretical guarantees for maintaining information about dynamic graphs; i.e. graphs subject to change. The grant will fund two PhD students, a postdoc, and meetings with international collaborators.