Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity.

Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity.

Deterministic fully dynamic graph algorithms are presented for connectivity, minimum spanning tree, 2-edge connectivity, and biconnectivity. Assuming that we start with no edges in a graph with n vertices, the amortized operation costs are O(log2 n) for connectivity, O(log4 n) for minimum spanning f...

Ausführliche Beschreibung

Bibliographische Detailangaben
Veröffentlicht in:Journal of the ACM 48, 4 (2001).
1. Verfasser: Holm, Jacob
Format: Artikel
Sprache:English
Schlagworte:
Data.
Data structures.
Theory of computation.
Analysis of algorithms and problem complexity.
Nonnumerical algorithms and problems.
Computations on discrete structures.
Mathematics of computing.
Discrete mathematics.
Graph theory.
Graph algorithms.
Algorithms.