Sparsification-a technique for speeding up dynamic graph algorithms.

Sparsification-a technique for speeding up dynamic graph algorithms.

We provide data strutures that maintain a graph as edges are inserted and deleted, and keep track of the following properties with the following times: minimum spanning forests, graph connectivity, graph 2-edge connectivity, and bipartiteness in timeO(n1/2) per change; 3-edge connectivity, in time O...

Mô tả đầy đủ

Chi tiết về thư mục
Xuất bản năm:Journal of the ACM 44, 5 (1997).
Tác giả chính: Eppstein, David
Định dạng: Bài viết
Ngôn ngữ:English
Những chủ đề:
Mathematics of computing.
Discrete mathematics.
Graph theory.
Graph algorithms.
Theory of Computation.
Analysis of algorithms and problem complexity.
Algorithms.
Performance.