Academic Commons

Theses Doctoral

Dynamic Algorithms for Shortest Paths and Matching

Bernstein, Aaron

There is a long history of research in theoretical computer science devoted to designing efficient algorithms for graph problems. In many modern applications the graph in question is changing over time, and we would like to avoid rerunning our algorithm on the entire graph every time a small change occurs. The evolving nature of graphs motivates the dynamic graph model, in which the goal is to minimize the amount of work needed to reoptimize the solution when the graph changes. There is a large body of literature on dynamic algorithms for basic problems that arise in graphs. This thesis presents several improved dynamic algorithms for two fundamental graph problems: shortest paths, and matching.


  • thumnail for Bernstein_columbia_0054D_13506.pdf Bernstein_columbia_0054D_13506.pdf binary/octet-stream 503 KB Download File

More About This Work

Academic Units
Computer Science
Thesis Advisors
Stein, Clifford S.
Ph.D., Columbia University
Published Here
August 19, 2016