文献

J-GLOBAL ID：201002261644715028   整理番号：10A0777692

O(n)期待時間でのスパースランダムグラフにおける最大マッチングの発見

Finding a Maximum Matching in a Sparse Random Graph in O(n) Expected Time

著者 (3件)： CHEBOLU Prasad (Carnegie Mellon Univ., Pennsylvania) ,  FRIEZE Alan (Carnegie Mellon Univ., Pennsylvania) ,  MELSTED Pall (Carnegie Mellon Univ., Pennsylvania)
資料名： Journal of the ACM (Association for Computing Machinery)  (Journal of the ACM (Association for Computing Machinery))
巻： 57  号： 4  ページ： 24:1-24:27  発行年： 2010年04月 
JST資料番号： C0267A  ISSN： 0004-5411  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： アメリカ合衆国 (USA)  言語： 英語 (EN)

抄録/ポイント： グラフG(V,E)におけるマッチングMは頂点が互いに素な辺の集合である。最大サイズのマッチング計算問題はアルゴリズム理論の中心課題であり,平均的アルゴリズムはランダムグラフG_n,m上でO(m log n)期待時間で実行され,同様の結果となる。スパースランダムグラフにおける最大基数マッチングを発見するための,線形期待時間アルゴリズムを提示した。平均測度が十分な大きさの定数ならばO(n)期待時間で最大マッチングを発見でき,平均測度がnと共に増加する場合に容易に拡張できることを示した。提案手法は最適で,対数因子による既存手法を改良できた。

シソーラス用語： 無秩序系 ,  *マッチング ,  *計算量 ,  *最大化問題 ,  *グラフ理論 ,  組合せ論 ,  ツリー構造 ,  データ構造 ,  定理証明 ,  最適化手法 ,  計算機アルゴリズム
準シソーラス用語： ランダムグラフ ,  線形時間アルゴリズム

分類 (1件)： 計算理論  (JB02000A)

タイトルに関連する用語 (3件)： 期待 ,  最大マッチング ,  発見