文献

J-GLOBAL ID：201702246074153237   整理番号：17A1419276

最小平均サイクルを見つける方法【Powered by NICT】

A note on finding minimum mean cycle

著者 (2件)： Chaturvedi Mmanu (Department of Computer Science, Colorado State University, Fort Collins, CO 80523-1873, USA) ,  McConnell Ross M. (Department of Computer Science, Colorado State University, Fort Collins, CO 80523-1873, USA)
資料名： Information Processing Letters  (Information Processing Letters)
巻： 127  ページ： 21-22  発行年： 2017年 
JST資料番号： E0513A  ISSN： 0020-0190  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： オランダ (NLD)  言語： 英語 (EN)

抄録/ポイント： エッジ重みを持つ有向グラフでは,有向サイクルの平均重量は,そのエッジの数で割った量である。グラフの最小サイクル平均はサイクルの最小平均重みである。Karpは最小サイクル平均の特性化とそれを計算するO(n m)アルゴリズムを与え,nは頂点の数であり,mは辺の数であった。しかし,この平均量サイクルを同定するための提案したアルゴリズムが正しくない。代替法を提案した。Copyright 2017 Elsevier B.V., Amsterdam. All rights reserved. Translated from English into Japanese by JST.【Powered by NICT】

シソーラス用語： キャラクタリゼーション ,  アルゴリズム ,  有向グラフ ,  *グラフ

著者キーワード (3件)： アルゴリズムの解析 ,  アルゴリズムの設計 ,  グラフアルゴリズム

分類 (2件)： グラフ理論基礎  (IA02020S) ,  計算理論  (JB02000A)

タイトルに関連する用語 (2件)： 平均 ,  サイクル