Showing 2025Show all
2 papers · 1 filter
cs.DS2025
Deterministic Lower Bounds for -Edge Connectivity in the Distributed Sketching Model
Peter Robinson, Ming Ming Tan
We study the -edge connectivity problem on undirected graphs in the distributed sketching model, where we have nodes and a referee. Each node sends a single message to the r…
cs.DC2025
Perfect Matching with Few Link Activations
Hugo Mirault, Peter Robinson, Ming Ming Tan +1
We consider the problem of computing a perfect matching problem in a synchronous distributed network, where the network topology corresponds to a complete bipartite graph. The comm…