On k-component Algorithms for Graphs and Digraphs

• Item type: National Convention(1)
• 公開日: 1988-09-12
• タイトル / 言語: en
• タイトル: On k-component Algorithms for Graphs and Digraphs
• 言語: eng
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_5794
• 資源タイプ: conference paper
• 著者所属(英): en
• 著者所属(英): IBM Research, Tokyo Research Laboratory
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Consider a digraph (or graph) G without any self-loops on parallel-edges. We denote the vertex-set and edge-set of G by V(G) and E(G), respectively. We denote the candinality of V(G) and E(G), namely, |V(G)| or |E(G)| by n and e, respectively. G is k-connected, if there exist at least k vertex-disjoint paths from v to w, for every ordered pair of v and w (v, w ∈ V(G)). A k-component of G is a maximal k-connected subgraph of G (see Figure 1). Hopcroft and Tarjan discovered algorithms for finding 1-components, 2-conponents and 3-components of a graph, as well as 1-components of a digraph, within O(n+e) time [Ta72], [HoTa73]. The existence of such linear algorithms for finding k-components of a graph for any fixed k(>3) was conjectured in [AhHoU174] ; however, no such linear algorithm has been found. Recently, Kanevsky and Ramachandran discovered an algorithm that finds all separating triplets of a 3-connected graph in O(n^2) time [KaRa87], which suggests the existence of an efficient algorithm for finding 4-components of a graph ; however, finding all separating triplets does not directly yield a decomposition into 4-components, and the problem still remains. Matula discovered a polynomial algorithm that finds all the k-components of a graph, using cluster analysis techniques [Ma77]. Note that the problems for graphs are easily reducible to those for symmetrical digraphs, although the converse is not true. Our purpose is to construct an algorithm to find all the k-components of a digraph. Our algorithm can be regarded as an extension and refinement (a practical, and probably more efficient version) of Matula's. Proceeding to our main results, we need to introduce some notations. For v, w∈V, let [v, w] denote a directed edge which leaves v and enters w. For v∈V, let Γ+(v)= {w|[v, w]∈E(G)}, and Γ-(v)={w|[w, v]∈E(G)}. We denote deg(v)=min{Γ+(v), Γ-(v)}. G is complete if Γ+(v)=Γ-(v)=n-1, for ∀v∈V(G). For U(⊂V(G)), ≪U≫_G denotes the induced subgraph of G by U, that is, a subgraph of G whose vertex-set is U, and whose edge-set is {[v, w]∈E(G)|v, w∈U}. S(⊂V(G)) is a separator of G if ≪V(G)＼S≫_G is not 1-connected. For l≥1, a l-separator, denoted by ζ^l(G), is a minimum separator, S, of G, such that |S|≤l, Note that ζ^l(G) is nothing but a minimum separator of G, if it exists, and that otherwise ζ^l(G) is empty (see Figure 1). We assume all digraphs in our algorithm are represented by adjacency structures [AhHoU174], [Ta72], and manipulated in an efficient way. Our results are summarized as follows.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN00349328
• 書誌情報: 全国大会講演論文集; 巻 第37回, 号 基礎理論および数値処理, p. 9-10, 発行日 1988-09-12
• 出版者 / 言語: ja
• 出版者: 情報処理学会