Decremental Dynamic Connectivity (Q4935307)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 1395725
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Decremental Dynamic Connectivity |
scientific article; zbMATH DE number 1395725 |
Statements
Decremental Dynamic Connectivity (English)
0 references
19 March 2000
0 references
\(k\)-edge-connectivity
0 references
0.8687203526496887
0 references
0.8564761281013489
0 references
0.8486258387565613
0 references
0.8483967185020447
0 references
The author gives a randomized algorithm for on-line connectivity problems with deletion only. Let \(G\) be a graph with \(m\) edges and \(n\) nodes. The algorithm maintains a spanning forest curing \(m\) edge-deletions in expected total time \[ O(m\log(n^2/m)+ n(\log n)^3(\log (m/(n\log n)))). \] It is based on a randomized reduction of many deletion-only queries to few deletions and insertions queries. This reduction works for general \(k\)-edge-connectivity problem.
0 references
