Dynamic Graph Connectivity

In a static graph, checking whether nodes are in the connected component takes linear time. I will describe the Kapron, King, Mountjoy algorithm supporting polylog time updates and queries.

Download Slides