著者

永持 仁 岩田 健吾 石井 利昌

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会技術研究報告. COMP, コンピュテーション (ISSN:09135685)

巻号頁・発行日

vol.103, no.31, pp.31-38, 2003-04-18

---

本研究では,グラフG= (V, E)と2つの素な節点集合(資源節点集合)T_1,T_2⊊V(|T_1|,|T_2| : 偶数)が与えられたとき,次の(i),(ii)を満たす節点集合の2分割{V_1,V_2}を見つける問題を考える。(i) |V_1∩T_j|=|V_2∩T_j|=|T_j|/2,j=1, 2, (ii) V_1とV_2が誘導するGのグラフはともに連結。この資源集合の均等問題はNP-困難であるが,入力グラフGが3点連結グラフならば,必ず(i),(iii)を満たすVの分割が存在し,そのような分割がO(|V|^2log|V|)時間,O(|V|+|E|)領域で求められることが知られている。このアルゴリズムでは,いったん入力グラフGを,凸埋め込みと呼ばれる配置として平面上に埋め込み,その埋め込みに対し,資源節点集合を均等分割するハムサンドイッチカット定理を適用することで,Vの分割を求めている。しかし,計算機上で実装する場合には,グラフの節点に対し実際に平面上の点座標を計算,格納することに伴う計算誤差のために,節点数の多い問題に対しては計算が破綻する恐れがある。本研究では,まず,凸埋め込みの方法について,従来法よりも簡単に節点の配置場所を計算する方法を提案し,次に,各節点の座標を実際に計算する代わりに,各節点間の相対位置関係に基づいたデータ保持方法を提案する。新しいアルゴリズムはO (|V|^2)時間,O (|V|^2)領域でグラフの分割を求める。実行中に各セルの保持する数値は大きさ|V|以下の整数だけでよく,実装における問題点を解決することができる。