文献

J-GLOBAL ID：201602011592392657   整理番号：74A0222016

グラフの3連結成分への分割

Dividing a graph into triconnected components.

著者 (2件)： HOPCROFT J E ,  TARJAN R E
資料名： SIAM J Comput (Soc Ind Ap  (SIAM Journal on Computing (Society for Industrial and Applied Mathematics))
巻： 2  号： 3  ページ： 135-158  発行年： 1973年 
JST資料番号： D0944A  ISSN： 0097-5397  CODEN： SMJCAT  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： アメリカ合衆国 (USA)  言語： 英語 (EN)

抄録/ポイント： グラフの連結度を求めることは応用上も極めて重要である。ここては,グラフを3連結成分へ分割する問題を考察した。 従来,連結度を求める方法としてdepth-first searchが用いられており,これは無向グラフの2連結成分を決定したり,有向グラフの強連結成分を決定するのに効率の良い方法である。 ここではこの方法を3連結成分を求める問題に適用し,ランダムアクセス計算機によって0(V+E)の計算時間と記憶量で済む方法を与える。 ここに,V,Eはそれぞれグラフの節点と枝の数セある;写図5参19

シソーラス用語： グラフ理論 ,  探索問題 ,  平面グラフ
準シソーラス用語： 連結度

タイトルに関連する用語 (2件)： グラフ ,  連結成分