تجزیه سلسله‌مراتبی گراف دینامیک

عنوان یک سخنرانی است که این سه‌شنبه برگزار می‌شود. احتمالا شرکت درش خالی از لطف نباشد.

Zoom link for DIMAP seminar

Monika HenzingerTuesday, 14:00, Zoom (link on DIMAP seminar webpage)

Hierarchical decompositions in dynamic graph algorithms

A dynamic graph algorithm is a data structure that maintains a graph property while the graph undergoes a sequence of edge updates. In dynamic graph algorithms with polylogarithmic time per operation a hierarchical graph decomposition is typically maintained. We present various such hierarchies and the different types of invariants used to maintain them efficiently. They lead to very fast dynamic algorithms for connectivity, approximate matching, vertex cover, densest subgraph and set cover as well as for (Delta+1)-vertex coloring.