Melvin's digital garden

Dynamic Graph problems

CREATED: 200712310824 Speaker: Do Huy Hoang, CS5234 project

  • Fully dynamic graph ** insertion of edge ** deletion of edge
  • Dynamic forests ** cut(u,v) ** link(u,v) ** findroot(u)
  • Link-Cut tree ** concept of solid and dashed edges ** dashed edges are easy to cut ** each solid path is stored in a splay tree ** key = depth of node in actual tree
  • Euler tour tree, store in binary tree
  • Dynamic connectivity in graphs ** store log n spanning forests ** $F_0 \supseteq F_1 \supseteq \ldots \supseteq F_{\lg n}$ ** each tree in level i has $\leq n/2^i$ vertices

Links to this note