论文标题
在完全动态的无向图上进行连接性查询的动态跨越树（扩展版）
Dynamic Spanning Trees for Connectivity Queries on Fully-dynamic Undirected Graphs (Extended version)
论文作者
论文摘要
回答连接查询是完全动态图的基础，在这些图形上，边缘和顶点经常插入和删除。现有工作提出了具有最差案例保证的数据结构和算法。我们提出了一种新的数据结构，即动态树（D-Tree），以及算法来构建和维护它。 D-Tree是第一个扩展到具有数百万个顶点和边缘的完全动态图的数据结构，并且平均而言，答案的连接查询要比具有最坏情况保证的数据结构要快得多。
Answering connectivity queries is fundamental to fully dynamic graphs where edges and vertices are inserted and deleted frequently. Existing work proposes data structures and algorithms with worst-case guarantees. We propose a new data structure, the dynamic tree (D-tree), together with algorithms to construct and maintain it. The D-tree is the first data structure that scales to fully dynamic graphs with millions of vertices and edges and, on average, answers connectivity queries much faster than data structures with worst case guarantees.
