重み付きグラフの公平連結分割

小野村 歩  西関 隆夫  

誌名
電子情報通信学会論文誌 D   Vol.J98-D   No.3   pp.363-372
発行日: 2015/03/01
Online ISSN: 1881-0225
論文種別: 特集論文 (学生論文特集)
専門分野: 情報・システム基礎
キーワード: 
公平連結分割,  直並列グラフ,  部分k-木,  擬多項式時間,  

本文: PDF(1.8MB)
>>論文を購入


あらまし: 
各点に非負整数重みが付いているグラフGと正整数pが与えられたとき,Gから何本かの辺を除去して,Gp個の互いに共通な点をもたない連結部分グラフに分割し,部分グラフの点重みの合計の最大と最小の差をできるだけ小さくしたい.このような分割をGp-公平連結分割という.本文では,このようなp-公平連結分割が直並列グラフや部分k-木に対して擬多項式時間で求まり,特に点重みが全て1であるときには多項式時間で求まることを示す.