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...

Полное описание

Библиографические подробности

Опубликовано в::	Journal of the ACM 44, 5 (1997).
Главный автор:	Eppstein, David
Формат:	Статья
Язык:	English
Предметы:	Mathematics of computing. Discrete mathematics. Graph theory. Graph algorithms. Theory of Computation. Analysis of algorithms and problem complexity. Algorithms. Performance.