Dynamic Graph Problems

Download: Report , Slides


We designed eager methods (with amortized bounds) and lazy methods (with worst case bounds) to maintain maximal independent sets (MIS) in dynamic graphs, where changes may occur in the graph of interest. Properties of special graphs such as planar graphs and bounded arboricity graphs were exploited and we also considered approximate/error-tolerant methods for maintaining MIS. We conjectured that the lower bound of for maintaining MIS in dynamic graphs is $\Omega(deg(u))$.