Linear Algorithms for a k-partition Problem of Planar Graphs without Specifying Bases

スポンサーリンク

概要

• 論文の詳細を見る

• In this paper, we consider the following k-partition problem. Input: (1) an undirected graph G=(V,E) with n=|V| vertices and m=|E| edges; (2) S⊆(V∪E)(|S|≧k); (3) k distinct vertices and/or edges a_i(1≦i≦k)∈S; and (4) k natural numbers n_1, n_2, ..., n_k such that Σ^k_<i=l>n_i=|S|. Output: a partition S_1∪S_2∪...∪S_k of the specified set S such that for each i(1≦i≦k); (a) a_i∈S_i; (b) |S_i|=n_i; and (c) there is a connected subgraph G_i=(V_i,E_i)of G such that S_i⊆(V⊆(V_i∪E_i) and G_1, G_2, ...G_k are mutually edge-disjoint. The problem is called the mixed k-partition problem with respect to edge-disjointness and it is simply called the mixed k-partition problem unless confusion arises. Each a_i is called a base of the subgraph G_i and if all bases are not specified for the mixed k-partition problem; the problem is called the mixed k-partition problem without bases. In the mixed k-partition problem, if S=E then the problem corresponds to the k-edge-partition problem and if S⊆V then the problem corresponds to the k-vertex-partition problem with respect to edge-disjointness. The mixed k-partition problem becomes the k-vertex-partition problem if S=V and the condition "edge-disjointness" in (c) is replaced by "vertex-disjointness". It has been shown that the k-edge-partition problem and the k-vertpartition problem and respect to edge-disjointness always have solutions for every k-edge-connected graph and the mixed k-partition problem has a solution for every k-edge-connected graph. Although efficient algorithms are known for these problems provided that k is 1imited to 2 and 3, no polynomial algorithms are known so far as k≧4. On the other hand, if we conider the mixed k-partition problem without bases, the following results have been obtained: 1. For any k≧2, the mixed k-partition problem without bases can be solved in O(|V|√<|V|log_2|V|>)+|E|) time for every 4-edge-connected graph G=(V,E). 2. The mixed tripartition problem without bases can be solved in O(|V|^2) time for every 2-edge-connected graph G=(V,E). 3. The mixed 4-partition problem without bases can be solved in O(|E|^2) time for every 3-edge-connected graph G=(V,E). In this paper, we show that if the input graph is planar, all the mixed k-partition problems stated above can be solved in linear time.

• 一般社団法人情報処理学会の論文
• 1997-09-24

著者

• WADA Koichi

  Nagoya Institute of Technology

• Chen Wei

  Nagoya Institute of Technology

• Wada Koichi

  Nagoya Inst. Technol. Nagoya‐shi Jpn

関連論文

• An Optimal Certificate Dispersal Algorithm for Mobile Ad Hoc Networks(Discrete Mathematics and Its Applications)
• Linear Algorithms for a k-partition Problem of Planar Graphs without Specifying Bases
• Complexity of minimum certificate dispersal problem with tree structure (コンピュテーション)

スポンサーリンク