We present an efficient NC algorithm for finding a sparse k- edge-connectivity certificate of a multigraph G. Our algorithm runs in O((log kn)(log k)2(log n)2) time using O(k(n + m′)) processors on an ARBITRARY CRCW PRAM, where n and m′ stand for the numbers of vertices in G and edges in the simplified graph of G, respectively.
['Hiroshi Nagamochi', 'Toru Hasunuma']
An Efficient NC Algorithm for a Sparse k-Edge-Connectivity Certificate