O(log log n) Passes is Optimal for Semi-Streaming Maximal Independent Set.

Sepehr Assadi Christian Konrad Kheeran K. Naidu Janani Sundaresan

Published in: CoRR (2023)

Keyphrases

independent set
worst case
optimal solution
maximum weight
maximum independent set
data streams
multimedia
lower bound
dynamic programming
log log