連続帯域幅による多重彩色

グラフの帯域幅連続多重彩色
(Bandwidth Consecutive
Multicolorings of Graphs)
西関研究室
西川和秀
1
応用
－タスクスケジューリング
－周波数帯域割当て
タスクの完了に必要な時間
4 5
2
タスク間の実行で
離さなければならない時間
4
2
2
1
7
1
1
7
1
2
3
4
⇒中断なし
1
11単位時間
2
3
3
10
連続で実行しなければならない
0
0
1
10 11
4 56
5
実行完了時間
6
7
8
9
10
11
帯域幅連続多重彩色( 彩色)
自然数(色)集合
4 5
5 6
グラフ
2
正整数点重み
非負整数辺重み
条件
(1) 各点に連続した
個の
正整数(色)からなる集合
を割り当てる．
(2) 各辺
について，
の色と
の色は
以上離れている．
4
2
2
1
7
1
10 11 最大
12 13 最大
0
1
0
7
10
12
1
3
の彩色数
1
3
2
3
4 56
678
＝13
＝11
＝11
3
帯域幅連続多重彩色問題
( 彩色問題)
入力:
－グラフ
－重み関数
出力:
最適な彩色
最小
4
彩色の簡単な表現
4 5
2
4
2
2
1
条件
(1) 各点に連続した
個の
正整数(色)からなる集合
を割り当てる．
(2) 各辺
について，
の色と
の色は
以上離れている．
7
1
条件
0
1
0
7
(a)
(b)
(c)
10 11
1
10
3
1
2
3
4 5 6
for
5
既存研究
点彩色
:
多重彩色
:
帯域幅彩色 :
1かつ
0なる彩色
0なる彩色
(ただし連続でなくてもよい)
1なる彩色
本文の帯域幅連続多重彩色( 彩色)は，これらの一般化
6
結果
帯域幅連続多重彩色問題（彩色問題）
（1）直並列グラフ（⊆部分2木）
・擬多項式時間厳密アルゴリズム
・FPTAS（近似）
（2）部分 -木
・擬多項式時間厳密アルゴリズム
・FPTAS（近似）
※部分3木に対してNPC[MR’03]
7
直並列グラフの再帰的定義
1.
直並列グラフ
2.
直並列グラフ
直並列グラフ
直並列グラフ（直列接続）
直並列グラフ（並列接続）
なる彩色の最小スパン
10
8
2
2
1
2
2
2
1
0
1
・・・
2
0
1
・・・
2
1
存在しない
2
2
0
1
9
直並列グラフ
色
10
直並列グラフ
普通の点彩色数
最大重み
2
4
2
2
だけを計算すればよい
7
1
0
1
0
7
1
3
2
3
11
厳密アルゴリズム
直並列グラフ
条件
(a)
満たす
(b)
(c)
for
満たさない
12
時間計算量
並列接続
時間
直並列グラフ
（並列接続）
直列接続
時間
直並列グラフ
（直列接続）
擬多項式時間厳密アルゴリズム
の個数
が多項式ならば
の計算
並列接続または
も多項式
直列接続の回数
13
FPTAS(Fully Polynomial-Time
Approximation Scheme)
近似誤差率
を任意に選択
時間計算量
が直並列グラフならば
近似解:
14
FPTAS(Fully Polynomial-Time
Approximation Scheme)
任意のグラフ
2
2
近似誤差率
を任意に選択
4
1
縮尺率を適切に決める
の最適解
正整数
新しい重み
1
新しい最大重み
1 1
時間計算量
が直並列グラフならば
3
1
2
1
4
重み
6
なる
の彩色(近似解)
2
近似解
2
7
2 1
6
2
4
7
2
15
12
部分 -木へ拡張
例
3-木
部分3-木 : 3-木の任意の部分グラフ
を求める擬多項式時間厳密アルゴリズム
を近似するFPTAS
16
結果
帯域幅連続多重彩色問題（彩色問題）
（1）直並列グラフ（ ⊆部分2木）
・擬多項式時間厳密アルゴリズム
・FPTAS（近似）
（2）部分 -木
・擬多項式時間厳密アルゴリズム
・FPTAS（近似）
17
今後の課題
時間計算量
などの改善
18
発表文献
• 国際会議
– K. Nishikawa, T. Nishizeki and X. Zhou, Algorithms
for bandwidth consecutive multicolorings of
graphs (Extended Abstract), Proc. FAW-AIIM 2012,
Lecture Notes in Computer Science, Vol. 7285,
pp.117-128, 2012.
• Journal
– K. Nishikawa, T. Nishizeki and X. Zhou, Bandwidth
consecutive multicolorings of graphs, Theoretical
Computer Science, to appear.
19
なぜ辺重みは正整数でないのか？
• 回答
– 非負整数とすると、
が
綺麗に特徴付けられるから．
20
なぜ辺重みは正整数でないのか？
• 回答
– 非負整数とすると、
が
綺麗に特徴付けられるから．
の無閉路向き付け
の最長有向路の長さ
21
1．基本的な性質
補題3.どんな重み付きグラフに対しても，
の無閉路向き付け
の無閉路向き付け
有向道
2
2
有向道
の長さ
4
＝1+2+2+4+2＝
11
7
最長有向道
0
最長路
の長さ
・・・有向道
1
0
1
0
7
1 ＝11
3
2 有向閉路
3
4
2
2
1
最長路
の長さ
2
2
＝3+2+1+0+2＝
8
7
0
の長さ
1
＝3+2+1+7+1+0+1+7+2＝
24
7
最長有向道 1 の長さ
無閉路向き付けではない無閉路向き付け
3
＝24
2
3
22
1．基本的な性質
補題3.どんな重み付きグラフに対しても，
=11
2
2
4
2
最長路
4
2
2
7
1
・・・
0
1
0
最長路
2
2
3
1
7
2
1
3
＝24
0
0
7
1
7
1
3
・・・
3
＝11
23
2
2
4
2
4
2
2
1
7
2
0
1
2
1
4
0
1
1
0
1
4
1
2
3
3
1
1
2
1
2
1
7
3
3
0
0
2
1
1
7
1
7
1
1
0
0
1
2
4
0
1
4
1
2
1
2
一般のグラフ
部分 -木
:定数
部分3-木
直並列グラフ
(部分2-木)
木
:点数
25
彩色の簡単な表現
逆に
が(a)(b)(c)を満たす
が(1)(2) を満たす
条件
(a)
(b)
(c)
同値
for
26
彩色の簡単な表現
条件
(a)
(b)
(c)
for
27
彩色の簡単な表現
(c)
for
正
条件(2)を満たす
28
1．基本的な性質
補題1. どんな重み付きグラフに対しても，
最大重み
普通の彩色数
色1
証明.
の部分集合
独立
色2
色
独立
独立
は彩色
独立
色3
29
1．基本的な性質
二部グラフや木に対しては線形時間で最適な彩色が求まる
補題2.
を二部グラフまたは木とし，
とする．この時，
証明.
彩色
は自明
を証明する
の部分集合
の部分集合
の証明
：最適な彩色，
6
の向き付け
2
1
for
2
2
は無閉路的
3
1
0
1
閉路があるならば
閉路はない
31
2
1
の証明
2
2
1
0
なる無閉路的向き付け
においてへ行く最長
有向道の長さ
6
条件
2
1
(a)
2
(b)
(c)
2
3
のとき
非負
0
1
1
正
32
2
1
の証明
2
2
1
0
なる無閉路的向き付け
においてへ行く最長
有向道の長さ
6
条件
2
1
(a)
2
(b)
(c)
2
3
のとき
非負
0
1
1
正
なので矛盾
逆向き
33
6
の証明
2
1
：最適な彩色，
2
2
の向き付け
for
1
0
3
1
6
2
は無閉路的
の最長有向道
1
2
2
道
(a)
(c)
(c)
(c)
(c)
条件
1
0
3
1
(a)
(b)
・・・・・・・・・・・
(c)
for
34
2
1
の証明
2
2
1
0
なる無閉路的向き付け
においてへ行く最長
有向道の長さ
6
2
1
は条件(a)(b)(c)を満たすので，
は
彩色
2
2
0
3
1
1
は最適とは限らない
□
35
直並列グラフ
直並列グラフ
直並列グラフ
直並列グラフ（直列接続）
直並列グラフ（並列接続）
FPTAS(Fully Polynomial-Time
Approximation Scheme)
任意のグラフ
2
2
近似誤差率
を任意に選択
の最適解
縮尺率を適切に決める
1 1
重み
1
3
1
1
4
2
4
1
6
なる
6
の彩色(近似解) 2
2
2
厳密アルゴリズムは
と
の多項式時間
2
7
1
7
4
2
37
12
は
の
彩色
条件
(a)
両辺に
(b)
両辺に
(c)
の最適解
for
両辺に
条件
(a)
1
1 1
重み
2
2
3
1
1
4
2
4
1
6
なる
6
の彩色(近似解) 2
2
(b)
2
(c)
for
条件(a)(b)(c)より，
は彩色
2
7
1
7
4
2
38
12
厳密アルゴリズム（直列接続）
直並列グラフ
（直列接続）
時間
39
厳密アルゴリズム（並列接続）
直並列グラフ
（並列接続）
時間
40
補題5.
2
任意のグラフ
4
2
の任意の無閉路向き付け
2
1
7
0
の最長路
0
任意の正整数
の重みが
1
7
2
1
のグラフ
3
3
と同じ向き付け
の最長路
1
2
1
1
1
4
0
0
1
4
1
1
2
2
41
の証明
2
4
2
両辺に
2
1
7
0
0
1
7
2
1
3
3
は最長
1
2
1
1
1
4
0
0
両辺をで割ると
1
4
1
1
2
2
□
42
任意のグラフ
補題4.
近似解
最適解
証明．
が最小になる
の無閉路向き付け
の最長路
誤差
高々
補題３より
両辺に
43
上の式
の最長路
誤差
高々
証明は省略するが
誤差
高々
両辺に
誤差
高々
補題3より
両辺に
両辺に
□
最長路が最小になる
44
の向き付け
補題4.
証明．
任意のグラフ
近似解
最適解
が最小になる
の無閉路向き付け
の最長路
誤差
高々
誤差
高々
誤差
高々
□
最長路長が最小になる
の無閉路向き付け
近似解
46
定理．
グラフのクラスに対し，彩色問題を，とに関する多項式時間
で解く厳密アルゴリズムがあるならば，クラスに対してFPTASが存在す
る．
直並列グラフに対し，彩色問題をと
で解く厳密アルゴリズムがあるので，
に関する多項式時間
定理よ
り，
系1．
直並列グラフの彩色問題に対してFPTASが存在する．
その時間計算量は
47
グラフの帯域幅連続多重彩色( 彩色)
1.
彩色の基本的な性質
2. 直並列グラフに対する擬多項式時間厳密アルゴリズム
: 点数
3. 直並列グラフに対する近似アルゴリズム，FPTAS
: 任意の誤差率
4. 部分 -木への拡張
5. 結論
48
-木の再帰的定義
1.
点からなる完全グラフは木である．
-木
2.
が木であり，その点が完全グラフを誘導するとき，新しい１点を追加し，
それら点と辺で結んで得られるグラフも木である．
-木
-木
49
3-木
1.
点からなる完全グラフは木である．
3-木
2.
が木であり，その点が完全グラフを誘導するとき，新しい１点を追加し，
それら点と辺で結んで得られるグラフも木である．
3-木
50
部分 -木
部分 -木: -木の部分グラフ
3-木
部分3-木
51
分解木
部分3-木
分解木
52
分解木
・・・
・・・
分解木
53
-木へ拡張
部分 -木
端子が
+1個
・・・
補題1.
なる彩色の最小スパン
だけを計算すればよい
54
時間計算量
接続
時間
の個数
の計算
接続の回数
擬多項式時間
厳密アルゴリズム
55
定理．
グラフのクラスに対し，彩色問題を，とに関する多項式時間
で解く厳密アルゴリズムがあるならば，クラスに対してFPTASが存在す
る．
部分 -木に対し，彩色問題をとに関する多項式時間
で解く厳密アルゴリズムがあるので，
定理より，
系2．
部分 -木の彩色問題に対してFPTASが存在する．
その時間計算量は
56
アルゴリズム
・・・
・・・
57
3-木
1.
点からなる完全グラフは木である．
3-木
2.
が木であり，その点が完全グラフを誘導するとき，新しい１点を追加し，
それら点と辺で結んで得られるグラフも木である．
3-木
58
結果
帯域幅連続多重彩色問題（彩色問題）
（1）直並列グラフ（部分2木）
・擬多項式時間厳密アルゴリズム
・FPTAS（近似）
（2）部分 -木
・擬多項式時間厳密アルゴリズム
・FPTAS（近似）
59

Download Report