グラフの指定点3点連結化問題に対する解法

• Item type: SIG Technical Reports(1)
• 公開日: 1996-01-22
• タイトル: グラフの指定点3点連結化問題に対する解法
• タイトル / 言語: en
• タイトル: Solving the 3 -Vertex- Connectivity Augmentation Problem for Specified Set of Vertices of a Graph
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 広島大学工学部第二類回路システム工学講座
• 著者所属: 広島大学工学部第二類回路システム工学講座
• 著者所属(英): en
• 著者所属(英): Department of Circuits and Systems, Faculty of Engineering, Hiroshima University
• 著者所属(英): en
• 著者所属(英): Department of Circuits and Systems, Faculty of Engineering, Hiroshima University
• 著者名: 間島, 利也; 渡邉, 敏正
• 著者名(英): Toshiya, Mashima; Toshimasa, Watanabe
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 指定点3点連結化問題(VCA?S)とは，無向グラフG=(，)と指定点集合S⊆Vが与えられたときに，Gに辺を付加することにより，どの2点を除去してもSの全ての点が1つの連結成分に含まれるようなグラフとなる最小の付加辺集合を求める問題である．本稿では，Gが2点連結である場合の3VCA?SVに対する線形時間アルゴリズムを示す．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: The 3-Vertex-Connectivity Augmentation problem for Specified set of Vertices (3VCA-SV) is defined as follows: Given an undirected graph G = (V,E) and a specified set of vertices S⊆V, find a smallest set of edges to be added to G so that the resulting graph may have the property that, even after deleting any two vertices from it, all vertices in S are contained in one connected component. This paper proposes a linear time algorithm for solving 3VCA-SV where G is 2-vertex-connected.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 情報処理学会研究報告アルゴリズム（AL）; 巻 1996, 号 9(1995-AL-049), p. 17-24, 発行日 1996-01-22
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会