MISC

2001年

An Efficient script N signScript C sign Algorithm for a Sparse k-Edge-Connectivity Certificate

Journal of Algorithms
  • Hiroshi Nagamochi
  • ,
  • Toru Hasunuma

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.

リンク情報
DOI
https://doi.org/10.1006/jagm.2000.1144

エクスポート
BibTeX RIS