Bipartition of Biconnected Graphs

• Item type: National Convention(1)
• 公開日: 1989-10-16
• タイトル / 言語: en
• タイトル: Bipartition of Biconnected Graphs
• 言語: eng
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_5794
• 資源タイプ: conference paper
• 著者所属(英): en
• 著者所属(英): Tohoku University
• 著者所属(英): en
• 著者所属(英): Tohoku University
• 著者所属(英): en
• 著者所属(英): Tohoku University
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: We present a linear algorithm for solving bipartition problem for a biconnected graph. The bipartition problem is the following : Input : (1) an undirected graph G=(V, E) with n=|V| vertices and m=|E| edges ; (2) s_1, s_2 ∈ V, s_1 ≠ s_2 ; and (3) two natural numbers n_1, n_2 ∈ N such that n_1 + n_2 = n. Output : a partition(V_1, V_2)of vertex set V such that (a) s_1 ∈ V_1 and s_2 ∈ V_2 ; (b) |V_1| = n_1 and |V_2| = n_2 ; and (c) V_1 and V_2 induce connected subgraphs of G. Fig. 1 depicts an instance of the problem above and a solution. Clearly the problem has no solution for some graphs. Furthermore the problem determining whether theabove problem has a solution is NP-complete if G may be not biconnected [DF]. However, Gyori and Lovasz independently proved the following theorem. THEOREM 1 [Gy, Lo]. If G is k-partition problem has a solution. the k-partition problem is one to find k disjoint connected subgraphs in a graph each of which contains a specified vertex and has a specified number of vertices. Since the bipartition problem is a subproblem of k-partition problem, it necessarily has a solution if the given graph G is biconnected. Although the proof by Gyori provides a polynomial algorithm if k = 2, naive implementation of the algorithm does not run in linear time. Our algorithm is not based on the proofs but based on characteristics of a depth first search tree in a biconnected graph.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN00349328
• 書誌情報: 全国大会講演論文集; 巻 第39回, 号 情報理論及び基礎技術, p. 71-72, 発行日 1989-10-16
• 出版者 / 言語: ja
• 出版者: 情報処理学会