文献

J-GLOBAL ID：201702227235699846   整理番号：17A1396015

すべて幅有向グラフにおける最初の全スパンニング木発見【Powered by NICT】

Finding All Breadth First Full Spanning Trees in a Directed Graph

著者 (2件)： Khalil Hoda ,  Labiche Yvan
資料名： IEEE Conference Proceedings  (IEEE Conference Proceedings)
巻： 2017  号： COMPSAC  ページ： 372-377  発行年： 2017年 
JST資料番号： W2441A  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： アメリカ合衆国 (USA)  言語： 英語 (EN)

抄録/ポイント： 幅優先探索有向グラフ横断に基づいていることをすべての可能な異なる全域木を生成すると特に関係するアルゴリズムを提案した。発生した樹木は,すべての端やオリジナル有向グラフの頂点にわたっている。アルゴリズムは初期トリーを発生させることから始めると,初等変換を用いた樹木の残りの部分を生成する。Eはエッジの数はO(E+T)時間で実行されるとTは生成された樹木の数である。最悪のシナリオでは,Nは元のグラフ中のノードの数これはO(E+En/Nn)時間計算量と同等であった。アルゴリズムはO(T)空間を必要とする。アルゴリズム空間計算量を改善するための可能な修正を示唆した。さらに,実験は,アルゴリズムの性能を評価するために実施し,結果を表に示した。Copyright 2017 The Institute of Electrical and Electronics Engineers, Inc. All Rights reserved. Translated from English into Japanese by JST【Powered by NICT】

シソーラス用語： アルゴリズム ,  *有向グラフ ,  *スパンニング木 ,  計算量
準シソーラス用語： 時間計算量 ,  幅優先探索 , 【Automatic Indexing@JST】

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

タイトルに関連する用語 (3件)： 有向グラフ ,  スパンニング木 ,  発見