木の公平p -分割問題発表者西関研究室 8710 築山 2015/10/1 伸一 1 （入力）１．木T p -分割問題各点v には正整数の重みw (v )が付いている２．正整数p,ℓ,u （ℓ ≤u） Tからp-1本の辺を除去して得られる（出力） p本の部分木𝑇1 , 𝑇2 , … , 𝑇𝑝 ただし、1≤ 𝑖 ≤p なる各 𝑖 について ℓ ≤w (𝑇𝑖 )≤u ※w (𝑇𝑖 )= 𝑣∈𝑇𝑖 𝑤(𝑣) あるいは「存在しない」 2015/10/1 2 （例１）3-分割問題（ℓ = 3,u = 15） 2 3 3 9 4 3 3 ・重み付き木Ｔ 2015/10/1 １５ 9 3 3 4 2 2 1 ９ 2 1 1 1 ４・3本の部分木 3 木のp-分割問題を解くアルゴリズム O ( 𝑝4 𝑛 )時間 n : 点数, p : 部分木数 [文献] T. Ito, T. Nishizeki, M. Schröder , T. Uno and X. Zhou Partitioning a Weighted Tree into Subtrees with Weights in a Given Range Algorithmica, 62, pp, 823-841, 2012. 2015/10/1 4 木の公平p-分割問題（入力）１．木T 各点v には正整数の重みw (v )が付いている２．正整数p （出力） Tからp -1本の辺を除去して得られる p本の部分木𝑇1 , 𝑇2 , … , 𝑇𝑝 への分割で、 max 𝑤(𝑇𝑖 ) − min 𝑤(𝑇𝑖 ) 𝑖 ※w (𝑇𝑖 )= 𝑖 𝑣∈𝑇𝑖 𝑤(𝑣) が最小であるもの ※すなわち公平である 2015/10/1 5 （例２）例１の分割（p=3） 2 3 2 15 3 3 9 3 3 9 3 3 2 2 1 1 ・重み付き木Ｔ max 𝑤(𝑇𝑖 ) − min 𝑤(𝑇𝑖 ) 𝑖 ※w (𝑇𝑖 )= 2015/10/1 𝑖 3 1 4 1 ・3本の部分木 15 - 4 = 11 𝑣∈𝑇𝑖 𝑤(𝑣) 6 （例3）例１の公平3-分割 2 3 3 3 2 8 9 3 3 3 9 3 3 2 2 1 1 ・重み付き木Ｔ max 𝑤(𝑇𝑖 ) − min 𝑤(𝑇𝑖 ) 𝑖 ※w (𝑇𝑖 )= 2015/10/1 𝑖 1 10 1 ・3本の部分木 10 - 8 = 2 𝑣∈𝑇𝑖 𝑤(𝑣) 7 （応用）土地のp＝3人への分割２３９３３３２１ 2015/10/1 １ 8 （応用）土地のp＝3人への分割２９９３８３１０３２１ 2015/10/1 ３１ 9 今後の課題公平p-分割問題をできるだけ速く解くアルゴリズムを考案する. 2015/10/1 10