Dynamic Spanning Trees for Connectivity Queries on Fully-dynamic Undirected Graphs (Extended version)

Qing Chen, Oded Lachish, Sven Helmer +1

Answering connectivity queries is fundamental to fully dynamic graphs where edges and vertices are inserted and deleted frequently. Existing work proposes data structures and algor…