Incremental ( 𝒌, 𝒛 ) -Clustering on Graphs
A randomized incremental ( 𝑘, 𝑧 ) -clustering algorithm that maintains with high probability a constant-factor approximation in a graph undergoing edge insertions with a total update time of ˜ 𝑂 ( 𝑘𝑚 1 + 𝑜 ( 1 ) + 𝑘 1 + 1 𝜆 𝑚 ) , where 𝜆 ≥ 1 is an arbitrary fixed constant.
Emilio Cruciani, Sebastian Forster, Antonis Skarlatos
· 0 citations