Improving a long chain of works we obtain a randomized EREW PRAM algorithm for finding the connected components of a graph G=(V,E) with n vertices and m edges in O(log n) time using an optimal number of O((m+n)/log n) processors. The result returned by ...
A spectral sparsifier of a graph G is a sparser graph H that approximately preserves the quadratic form of G, i.e., for all vectors x, xTLGx ≈ xTLHx, where LG and LH denote the respective graph Laplacians. Spectral sparsifiers generalize cut sparsifiers,...
We present a randomized distributed maximal independent set (MIS) algorithm for arbitrary graphs of size n that halts in time O(logn) with probability 1−o(n−1), each message containing 1 bit: thus its bit complexity per channel is O(logn) (the bit ...
Association for Computing Machinery
New York, NY, United States
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in