（n-p）-点連結性のO（m+np3.5）時間判定法

• Item type: SIG Technical Reports(1)
• 公開日: 1996-10-17
• タイトル: （n-p）-点連結性のO（m+np3.5）時間判定法
• タイトル / 言語: en
• タイトル: An O (m+np3.5) time algorithm for determining a given graph is (n - p) -node- connected
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 豊橋技術科学大学情報工学系
• 著者所属: 豊橋技術科学大学情報工学系
• 著者所属(英): en
• 著者所属(英): Department of Information and Computer Sciences Toyohasi University of Technology
• 著者所属(英): en
• 著者所属(英): Department of Information and Computer Sciences Toyohasi University of Technology
• 著者名: 伊藤大雄; 横山, 光雄
• 著者名(英): Hiro, Ito; Mitsuo, Yokoyama
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 与えられたグラフG=(，)、整数1〓p〓nに対し、Gが(?)?点連結であるか否かを判定し、(?)?点連結である場合にはその点連結度も計算するO(+np^<3．5>）時間のアルゴリズムを与える（但しn=|V|，m=|E|）。また、与えられたグラフの点連結度を計算するO(+n(?K(））^<3．5>）時間のアルゴリズムも与える。これら2つのアルゴリズムはそれぞれ同じ計算時間のオーダーで、与えられたグラフの補グラフG^cに関して(?)?点連結性の判定や点連結度の計算問題を解くアルゴリズムにも拡張できる。
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: For a given graph G=(V,E) and a given integer 1〓p〓n, an O(m+np^<3.5>) time algorithm for determining whether or not G is (n-p)-node-connected and also calculating the node-connectivity when G is (n-p)-node-connected is presented, where n=|V| and m=|E|. For calculation of the node-connectivity of a given graph G, an O(m+n(n-K(G))^<3.5>) time algorithm is also presented. These two algorithms can be extended to the same problems on the complement graph of a given graph in the same time-complexity, respectively.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 情報処理学会研究報告アルゴリズム（AL）; 巻 1996, 号 100(1996-AL-054), p. 57-64, 発行日 1996-10-17
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会