直並列グラフの連続多重彩色 西関研究室 吉田進太郎

連続多重彩色問題 グラフ G=(V,E) 自然数の重み ω(v)∈ℕ (ℕ は自然数(色)の集合) 連続多重彩色(ω彩色) F : V→ 2ℕ F(v)は連続しているω(v)個の自然数(色) (v,w)∈E ⇒ F(v) ∩ F(w) = φ 4 2 2 1 3 3

連続多重彩色問題 グラフ G=(V,E) 自然数の重み ω(v)∈ℕ (ℕ は自然数(色)の集合) 連続多重彩色(ω彩色) F : V→ 2ℕ F(v)は連続しているω(v)個の自然数(色) (v,w)∈E ⇒ F(v) ∩ F(w) = φ {4,5,6,7} {6,7} 4 2 連続多重彩色ではない {1,2} 2 {1} 1 {4,6,9} {3,5,7} 3 3

連続多重彩色問題 グラフ G=(V,E) 自然数の重み ω(v)∈ℕ (ℕ は自然数(色)の集合) 連続多重彩色(ω彩色) F : V→ 2ℕ F(v)は連続しているω(v)個の自然数(色) (v,w)∈E ⇒ F(v) ∩ F(w) = φ 辺で結ばれた点に同じ色(数字)は使えない {4,5,6,7} {6,7} 4 2 {1,2} 2 {1} 1 {4,6,9} {3,5,7} 3 3 連続した色(数字)を割り当てなければならない

連続多重彩色問題 グラフ G=(V,E) 自然数の重み ω(v)∈ℕ (ℕ は自然数(色)の集合) 連続多重彩色(ω彩色) F : V→ 2ℕ F(v)は連続しているω(v)個の自然数(色) (v,w)∈E ⇒ F(v) ∩ F(w) = φ {3,4,5,6} {7,8} 4 2 連続多重彩色である {1,2} 2 {1} 1 {5,6,7} {2,3,4} 3 3

連続多重彩色問題 グラフ G=(V,E) 自然数の重み ω(v)∈ℕ (ℕ は自然数(色)の集合) 連続多重彩色(ω彩色) F : V→ 2ℕ ⇔ f : V→ℕ f のスパン {3,4,5,6} {7,8} 4 2 {1,2} 2 {1} 1 {5,6,7} {2,3,4} 3 3

連続多重彩色問題（ω彩色問題） グラフ G=(V,E) 自然数の重み ω(v)∈ℕ (ℕ は自然数(色)の集合) 連続多重彩色(ω彩色) F : V→ 2ℕ ⇔ f : V→ℕ Gのω彩色数 {3,4,5,6} {7,8} {5,6,7,8} {1,2} 2 4 2 4 {1,2} {3,4} 2 {1} ・・・ 2 {3} 1 1 3 3 {5,6,7} 3 {2,3,4} {5,6,7} 3 {8,9,10}

中断なしタスクスケジューリング 点 ：タスク 辺 ：同時に実行できないタスク 重み：仕事にかかる時間 ※各タスクは中断を認めない taskA taskB {3,4, 5, 6} {7, 8} 点 ：タスク 辺 ：同時に実行できないタスク 重み：仕事にかかる時間 ※各タスクは中断を認めない 　　→連続(Non-preemptive) 2 4 taskF 2 taskC {1,2} 1 {1} taskD taskE 3 3 {2, 3,4} {5, 6, 7} taskB taskE taskA taskD taskF taskC 1 2 3 4 5 6 7 8

既存研究 [周・西関 (2004)] の結果 多重彩色問題 ・・・ NP困難 直並列グラフに限定 ・・・ 線形時間 本研究 直並列グラフに限定　・・・　線形時間 連続している必要はない {1,2,4,7} {3,8} 2 4 本研究 {5,6} 2 {1} 1 直並列グラフの連続多重彩色問題 厳密アルゴリズム 近似アルゴリズム 3 {2,3,4} 3 {5,6,7}

直並列グラフの再帰的定義 (1)直並列グラフ(一本の辺) (2)直並列グラフG1, G2 G1 G2 (3.1)直並列グラフ(直列接続) s t (2)直並列グラフG1, G2 s2 t2 G1 G2 s1 t1 (3.1)直並列グラフ(直列接続) (3.2)直並列グラフ(並列接続) G1 G1 t2 t1 = s2 s1 = s2 t1 = t2 s1 G2 G2

擬多項式時間厳密アルゴリズム W : 最大点重み ：端子s に割り当てる最大の整数がi であり n : グラフの点数 を順々に計算していく 直列接続の場合： 並列接続の場合： 接続回数は高々 は 個 W : 最大点重み n : グラフの点数 ：端子s に割り当てる最大の整数がi であり 　t の最大の整数がj であるようなω彩色の最小スパン

完全多項式時間近似スキーム 達成したい近似率 ε (0 < ε < 1) に対し、縮尺率σを ⌊εW/2n⌋ (正整数) と定める 新たに ωσ(v) = ⌈ω(v)/σ ⌉ を重みとしたG と同形のGσ の ωσ 彩色 fσ を求める 直並列グラフの連続多重彩色問題に対し完全多項式時間近似スキームが存在し、 その計算時間は = O (n4/ε3 ) ( Wσ = ⌈W /σ ⌉ ) G Gσ 2 1 4 2 σ = 2 2 1 1 1 3 2 3 2

完全多項式時間近似スキーム 達成したい近似率 ε (0 < ε < 1) に対し、縮尺率σを ⌊εW/2n⌋ (正整数) と定める 新たに ωσ(v) = ⌈ω(v)/σ ⌉ を重みとしたG と同形のGσ の ωσ 彩色 fσ を求める 直並列グラフの連続多重彩色問題に対し完全多項式時間近似スキームが存在し、 その計算時間は = O (n4/ε3 ) ( Wσ = ⌈W /σ ⌉ ) G Gσ 3 4 2 1 4 2 σ = 2 1 1 2 1 1 1 3 2 3 5 2 3

完全多項式時間近似スキーム 達成したい近似率 ε (0 < ε < 1) に対し、縮尺率σを ⌊εW/2n⌋ (正整数) と定める 新たに ωσ(v) = ⌈ω(v)/σ ⌉ を重みとしたG と同形のGσ の ωσ 彩色 fσ を求める ⇒ Gの近似的に最適なω 彩色 f として f = σfσ を出力 ⇒ このとき σχωσ(Gσ) – χω(G) ≤ εχω(G) が証明できる 直並列グラフの連続多重彩色問題に対し完全多項式時間近似スキームが存在し、 その計算時間は = O (n4/ε3 ) ( Wσ = ⌈W /σ ⌉ ) G Gσ 6 8 3 4 2 1 4 2 σ = 2 1 2 2 1 2 1 f = σfσ 1 1 3 2 10 3 6 5 2 3

結論 直並列グラフの連続多重彩色に対し 擬多項式時間厳密アルゴリズム ： 完全多項式時間近似スキーム ： を与えた。 計算時間の改善が今後の課題である。 W : 最大点重み n : グラフの点数 ε：任意の実数 　　(0 < ε < 1)