k-辺連結性を保存する疎なグラフを求める効率の良いNCアルゴリズム
書誌事項
- タイトル別名
-
- An Efficient NC Algorithm for a Sparse k-Edge-Connectivity Certificate
この論文をさがす
説明
多重グラフGのk-辺連結性を保持する疎な全域部分多重グラフを、CRCW(ARBITRARY)PRAM上でO(k(n+m'))個のプロセッサを使用し、O((logkn)(logk)^2(logn)^2))時間で計算するNCアルゴリズムを与える。ここで、nはGの頂点数、m'はGを単純化して得られるグラフの辺の数を表す。
We present an efficient NC algorithm for finding a sparse k-edge-connectivity certificate of a multi-graph G. Our algorithm runs in O((logkn)(logk)^2(logn)^2)) time using O(k(n+m')) processors on a CRCW(ARBITRARY)PRAM, where n and m' stand for the numbers of vertices in G and edges in the simplified graph of G, respectively.
収録刊行物
-
- 電子情報通信学会技術研究報告. COMP, コンピュテーション
-
電子情報通信学会技術研究報告. COMP, コンピュテーション 98 (137), 39-46, 1998-06-23
一般社団法人電子情報通信学会
- Tweet
詳細情報 詳細情報について
-
- CRID
- 1570854177377034112
-
- NII論文ID
- 110003191664
-
- NII書誌ID
- AN10013152
-
- 本文言語コード
- en
-
- データソース種別
-
- CiNii Articles
