直並列グラフの連続多重彩色

直並列グラフの連続多重彩色
西関研究室
吉田進太郎
1
連続多重彩色問題
グラフ
G=(V,E)
ω(v)∈ℕ
自然数の重み
連続多重彩色(ω彩色)
(ℕ は自然数(色)の集合)
F : V→ 2ℕ
F(v)は連続しているω(v)個の自然数(色)
(v,w)∈E ⇒ F(v) ∩ F(w) = φ
4
2
2
1
3
2
3
連続多重彩色問題
グラフ
G=(V,E)
ω(v)∈ℕ
自然数の重み
連続多重彩色(ω彩色)
(ℕ は自然数(色)の集合)
F : V→ 2ℕ
F(v)は連続しているω(v)個の自然数(色)
(v,w)∈E ⇒ F(v) ∩ F(w) = φ
{4,5,6,7}
4
2
{6,7}
連続多重彩色ではない
{1,2}
{4,6,9}
3
2
1 {1}
3
3
{3,5,7}
連続多重彩色問題
グラフ
G=(V,E)
ω(v)∈ℕ
自然数の重み
連続多重彩色(ω彩色)
(ℕ は自然数(色)の集合)
F : V→ 2ℕ
F(v)は連続しているω(v)個の自然数(色)
辺で結ばれた点に同じ色(数字)は使えない
(v,w)∈E ⇒ F(v) ∩ F(w) = φ
{4,5,6,7}
4
{1,2}
{6,7}
2
{4,6,9}
4
2
3
3 {3,5,7}
連続した色(数字)を割り当てなければならない
1 {1}
連続多重彩色問題
グラフ
G=(V,E)
ω(v)∈ℕ
自然数の重み
連続多重彩色(ω彩色)
(ℕ は自然数(色)の集合)
F : V→ 2ℕ
F(v)は連続しているω(v)個の自然数(色)
(v,w)∈E ⇒ F(v) ∩ F(w) = φ
{3,4,5,6}
4
2
{7,8}
連続多重彩色である
{1,2}
{5,6,7}
5
2
1 {1}
3
3
{2,3,4}
連続多重彩色問題
グラフ
G=(V,E)
ω(v)∈ℕ
自然数の重み
連続多重彩色(ω彩色)
(ℕ は自然数(色)の集合)
F : V→ 2ℕ
⇔
f : V→ℕ
f のスパン
{3,4,5,6}
4
{1,2}
{5,6,7}
6
2
2
{7,8}
1 {1}
3
3
{2,3,4}
連続多重彩色問題（ω彩色問題）
グラフ
G=(V,E)
自然数の重み
ω(v)∈ℕ
連続多重彩色(ω彩色)
(ℕ は自然数(色)の集合)
F : V→ 2ℕ ⇔
f : V→ℕ
Gのω彩色数
{3,4,5,6}
2 {7,8}
4
{1,2} 2
{5,6,7} 3
7
1 {1}
3
{2,3,4}
{5,6,7,8}
・・・
2 {1,2}
4
{3,4} 2
{5,6,7} 3
1 {3}
3
{8,9,10}
中断なしタスクスケジューリング
taskA
{3,4, 5, 6}
taskB
2 {7, 8}
4
taskF
{1,2}
2
1
点：タスク
辺：同時に実行できないタスク
重み：仕事にかかる時間
taskC
{1}
※各タスクは中断を認めない
→連続(Non-preemptive)
3 taskD
3
taskE
{5, 6, 7}
{2, 3,4}
taskB
taskE
taskA
taskD
taskF
taskC
1
8
2
3
4
5
6
7
8
既存研究 [周・西関 (2004)] の結果
多重彩色問題・・・ NP困難
直並列グラフに限定・・・線形時間
連続している必要はない
本研究
{1,2,4,7}
2 {3,8}
4
{5,6} 2
1 {1}
直並列グラフの連続多重彩色問題
厳密アルゴリズム
近似アルゴリズム
9
{2,3,4} 3
3
{5,6,7}
直並列グラフの再帰的定義
(1)直並列グラフ(一本の辺)
s
t
(2)直並列グラフG1, G2
s2
G1
t1
s1
t2
G2
(3.1)直並列グラフ(直列接続)
G1
(3.2)直並列グラフ(並列接続)
t2
t1 = s2
s1
G2
10
G1
s1 = s2
t 1 = t2
G2
擬多項式時間厳密アルゴリズム
：端子s に割り当てる最大の整数がi であり
t の最大の整数がj であるようなω彩色の最小スパン
を順々に計算していく
直列接続の場合：
並列接続の場合：
接続回数は高々
は
11
個
W : 最大点重み
n : グラフの点数
完全多項式時間近似スキーム
達成したい近似率 ε (0 < ε < 1) に対し、縮尺率σを ⌊εW/2n⌋ (正整数) と定める
新たに ωσ(v) = ⌈ω(v)/σ ⌉ を重みとしたG と同形のGσ の ωσ 彩色 fσ を求める
直並列グラフの連続多重彩色問題に対し完全多項式時間近似スキームが存在し、
その計算時間は
= O (n4/ε3 ) ( Wσ = ⌈W /σ ⌉ )
G
Gσ
2
4
σ=2
2
1
3
12
3
1
2
1
1
2
2
完全多項式時間近似スキーム
達成したい近似率 ε (0 < ε < 1) に対し、縮尺率σを ⌊εW/2n⌋ (正整数) と定める
新たに ωσ(v) = ⌈ω(v)/σ ⌉ を重みとしたG と同形のGσ の ωσ 彩色 fσ を求める
直並列グラフの連続多重彩色問題に対し完全多項式時間近似スキームが存在し、
その計算時間は
= O (n4/ε3 ) ( Wσ = ⌈W /σ ⌉ )
G
Gσ
4
σ=2
2
1
3
13
3
2
3
1
1
2
1
5 2
4
1
2
3
1
完全多項式時間近似スキーム
達成したい近似率 ε (0 < ε < 1) に対し、縮尺率σを ⌊εW/2n⌋ (正整数) と定める
新たに ωσ(v) = ⌈ω(v)/σ ⌉ を重みとしたG と同形のGσ の ωσ 彩色 fσ を求める
⇒ Gの近似的に最適なω 彩色 f として f = σfσ を出力
⇒ このとき σχωσ(Gσ) –
χω(G) ≤ εχω(G) が証明できる
直並列グラフの連続多重彩色問題に対し完全多項式時間近似スキームが存在し、
その計算時間は
= O (n4/ε3 ) ( Wσ = ⌈W /σ ⌉ )
G
6
2
4
2 2
10 3
14
Gσ
8
1
3
6
2
σ=2
f = σfσ
1
3
1
2
1
5 2
4
1
2
3
1
結論
直並列グラフの連続多重彩色に対し
擬多項式時間厳密アルゴリズム：
完全多項式時間近似スキーム：
を与えた。
計算時間の改善が今後の課題である。
15
W : 最大点重み
n : グラフの点数
ε：任意の実数
(0 < ε < 1)

Download Report