Paper Info
Title
An efficient NC algorithm for a sparse k-edge-connectivity certificate
Abstract
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.
Year
DOI
Venue
1998
10.1006/jagm.2000.1144
International Symposium on Algorithms and Computation
Keywords
DocType
Volume
log k,arbitrary crcw pram,sparse k,efficient nc algorithm,edge-connectivity certificate,sparse k-edge-connectivity certificate,log kn,multigraph g.,log n
Conference
38
Issue
ISSN
ISBN
2
0302-9743
3-540-65385-6
Citations 
PageRank 
References 
0
0.34
10
Authors
2
Name
Order
Citations
PageRank
Hiroshi Nagamochi11513174.40
Toru Hasunuma214216.00