無向多重グラフのすべての3 ? 辺成分を求める線形時間アルゴリズム

• Item type: SIG Technical Reports(1)
• 公開日: 1991-05-29
• タイトル: 無向多重グラフのすべての3 ? 辺成分を求める線形時間アルゴリズム
• タイトル / 言語: en
• タイトル: Computing All 3 -Edge- Components of an Undirected Multigraph in Linear Time
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 広島大学工学部
• 著者所属: 広島大学工学部
• 著者所属: 広島大学工学部
• 著者所属(英): en
• 著者所属(英): Faculty of Engineering, Hiroshima University
• 著者所属(英): en
• 著者所属(英): Faculty of Engineering, Hiroshima University
• 著者所属(英): en
• 著者所属(英): Faculty of Engineering, Hiroshima University
• 著者名: 田岡, 智志; 渡辺, 敏正; 翁長, 健治
• 著者名(英): Satoshi, Taoka; Toshimasa, Watanabe; Kenji, Onaga
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 本稿の目的は与えられた多重辺無向グラフG=（，）のすべての3?辺成分を求めるO（|V|+|E|）時間アルゴリズムを提案することである．グラフの3?辺成分とはその中の任意の2点間に辺素なパスが3本以上存在するような極大な点集合である．提案アルゴリズムを使えば，Gが3?辺連結であるか否かをO（|V|+|E|）時間で判定でき，またGのすべてのカットペアをO（|V|^2+|E|）時間で求めることができる．アルゴリズムは深さ優先探索(）に基づく．一般性を失うことなくGは2?辺連結と仮定できる．1つのDFS木Tを固定するとき，カットペアは2つのタイプに分けられる:T上の枝と後退枝から成るtypelペア:T上の2本の枝から成るtype2ペアである．すべてのtype1ペアはO（|V|+|E|）時間で容易に求めることができる．重要な点はすべてのtype2ペアを含む枝集合KE（）がO（|V|+|E|）時間で求められることである．type1ペアかKE（）のいずれかに含まれる枝をGからすべて除去することによりGのすべての3?辺成分が求められる．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: The subject of the paper is to propose an O(|V|+|E|) algorithm for finding all 3-edge-components of a given multigraph G=(V,E). This algorithm can be used in deiecting whether G is 3-edge-connected or not in O(|V|+|E|) time, or can be modified into an O(|V|^2+|E|) algorithm for determining all cutpairs of G. An 3-edge-component of G is defined as a maximal set of vertices such that G has at least three edge-disjoint paths between everypair of vertices in the set. The algorithm is based on the depth-first search (DFS) technique. For any fixed DFS-tree T of G, cutpairs of G are partitioned into two types: a type 1 pair consists of an edge of T and a back edge; a type 2 pair consists of two edges of T. All type 1 pairs can easily be determined in O O(|V|+|E|) time. The point is that an edge set KE(T) in which any type 2 pair is included can be found in O O(|V|+|E|) time. All 3-edge-components of G appear as connected components if we delete from G all edges contained in type 1 pairs or in this edge set KE(T).
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 情報処理学会研究報告アルゴリズム（AL）; 巻 1991, 号 48(1991-AL-021), p. 1-8, 発行日 1991-05-29
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会