112 citations · 116 across the 10 of their papers we have counts for
Showing 2026Show all
2 papers · 1 filter
cs.DS2026
Testing Connectedness and Edge Connectedness
Diptaksho Palit, Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova +1
We revisit the classical problem of testing connectedness of graphs represented in the adjacency lists model and obtain optimal bounds. Specifically, we show that -tes…
cs.DS2026
Constrained Correlation Clustering: Towards Optimality
Sina Azizeddin, Evangelos Kipouridis, Nithin Varma
In the Correlation Clustering problem, we are given an undirected graph and are tasked with computing a clustering (partition of the nodes) that minimizes the number of violated pa…