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...
| Εκδόθηκε σε: | Journal of the ACM 48, 4 (2001). |
|---|---|
| Κύριος συγγραφέας: | |
| Μορφή: | Άρθρο |
| Γλώσσα: | Αγγλικά |
| Θέματα: |