2001年
An Efficient script N signScript C sign Algorithm for a Sparse k-Edge-Connectivity Certificate
Journal of Algorithms
- ,
- 巻
- 38
- 号
- 2
- 開始ページ
- 354
- 終了ページ
- 373
- 記述言語
- 英語
- 掲載種別
- 研究論文(学術雑誌)
- DOI
- 10.1006/jagm.2000.1144
- 出版者・発行元
- Academic Press
We present an efficient script N signScript C sign 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. © 2001 Academic Press.
- ID情報
-
- DOI : 10.1006/jagm.2000.1144
- ISSN : 0196-6774
- SCOPUS ID : 0347747981