Query Lower Bounds for Correlation Clustering under Memory Constraints

Sumegha Garg, Songhua He, Periklis A. Papakonstantinou

This work initiates the study of memory-query tradeoffs for graph problems, with a focus on correlation clustering. Correlation clustering asks for a partition of the vertices that…