グラフの帯域幅連続多重彩色 を求めるアルゴリズム 西川和秀，西関隆夫(関西学院大) 周 暁(東北大) 1 帯域幅連続多重彩色( 彩色) 自然数(色)集合 5 5 4 6 グラフ 2 正整数 点重み 非負整数 辺重み 条件 (1) 各点 に連続した 個の 正整数(色)からなる集合 を割り当てる． 4 2 2 1 7 1 について， の色と の色は 以上離れている． 12 11 13 10 0 1 0 7 1 3 10 12 (2) 各辺 最大 3 1 2 3 6 75 68 4 ＝13 11 の 彩色数 ＝11 2 帯域幅連続多重彩色問題 ( 彩色問題) 入力: － グラフ － 重み関数 出力: 最適な 彩色 最小 3 彩色 の簡単な表現 4 5 2 4 2 2 1 条件 7 1 0 1 0 7 (a) 1 10 (b) (c) 10 11 3 1 2 3 4 5 6 for 4 彩色 の簡単な表現 逆に が(a)(b)(c)を満たす が(1)(2) を満たす 条件 (a) (b) (c) 同値 for 5 応用 － タスクスケジューリング － 周波数帯域割当て タスクの完了に必要な時間 4 5 2 両端のタスク間の実行に空 けたい時間 4 2 2 1 7 1 1 7 1 3 4 連続(Non-preemptive) 1 2 3 3 10 2 タスクの中断は認めない 0 0 1 10 11 11単位時間 4 56 5 完了時間(makespan) 6 7 8 9 10 11 既存研究 点彩色 : 多重彩色 : 帯域幅彩色 : 1かつ 0なる 彩色 0なる 彩色 (ただし連続でなくてもよい) 1なる 彩色 本文の帯域幅連続多重彩色( 彩色)は，これらの一般化 7 木 直並列グラフ (部分2木) 部分3木 部分k木 一般のグラフ 点彩色 NPC 多重彩色 NPC 帯域幅彩色 NPC 帯域幅連続 多重彩色 (b彩色) NPC 8 一般のグラフ 部分 -木 :定数 部分3-木 直並列グラフ (部分2-木) 木 :点数 9 点彩色 木 直並列グラフ (部分2木) P P 部分3木 部分k木 [AP’89] P P 一般のグラフ NPC 多重彩色 NPC 帯域幅彩色 NPC 帯域幅連続 多重彩色 (b彩色) NPC 10 点彩色 多重彩色 木 直並列グラフ (部分2木) P P P P [ZN’04] 部分3木 部分k木 [AP’89] 一般のグラフ P P NPC P P [INZ’03] NPC 帯域幅彩色 NPC 帯域幅連続 多重彩色 (b彩色) NPC 11 点彩色 多重彩色 帯域幅彩色 帯域幅連続 多重彩色 (b彩色) 木 直並列グラフ (部分2木) P P P P [ZN’04] P ? 部分3木 部分k木 [AP’89] 一般のグラフ P P NPC P P [INZ’03] NPC NPC NPC [MR’03] FPTAS NPC NPC 12 本論文 点彩色 多重彩色 帯域幅彩色 帯域幅連続 多重彩色 (b彩色) 木 直並列グラフ (部分2木) P P P P [ZN’04] P O(n) [AP’89] ? 擬多項式時間 厳密アルゴリズム FPTAS 部分3木 部分k木 一般のグラフ P P NPC P P [INZ’03] NPC NPC NPC [MR’03] FPTAS NPC NPC FPTAS 本文 NPC NPC 13 グラフの帯域幅連続多重彩色( 彩色) 1. 彩色の基本的な性質 2. 直並列グラフに対する擬多項式時間厳密アルゴリズム : 点数 3. 直並列グラフに対する近似アルゴリズム，FPTAS : 任意の誤差率 4. 部分 -木への拡張 5. 結論 14 グラフの帯域幅連続多重彩色( 彩色) 1. 彩色の基本的な性質 2. 直並列グラフに対する擬多項式時間厳密アルゴリズム : 点数 3. 直並列グラフに対する近似アルゴリズム，FPTAS : 任意の誤差率 4. 部分 -木への拡張 5. 結論 15 1．基本的な性質 補題1. どんな重み付きグラフ に対しても， 最大重み 普通の点彩色数 色1 証明. の部分集合 独立 色2 色 独立 独立 は 彩色 独立 色3 16 1．基本的な性質 二部グラフや木に対しては線形時間で最適な 彩色が求まる 補題2. を二部グラフまたは木とし， とする．この時， 証明. 彩色 は自明 を証明する の部分集合 の部分集合 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 18 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 19 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 20 2 1 の証明 2 2 1 0 なる無閉路的向き付け において へ行く最長 有向道の長さ 6 2 1 は条件(a)(b)(c)を満たすので， は 彩色 2 2 0 3 1 1 は最適とは限らない □ 21 グラフの帯域幅連続多重彩色( 彩色) 1. 彩色の基本的な性質 2. 直並列グラフに対する擬多項式時間厳密アルゴリズム : 点数 3. 直並列グラフに対する近似アルゴリズム，FPTAS : 任意の誤差率 4. 部分 -木への拡張 5. 結論 22 直並列グラフの再帰的定義 1. 直並列グラフ 2. 直並列グラフ 直並列グラフ 直並列グラフ（直列接続） 直並列グラフ（並列接続） 23 なる 彩色 の最小スパン 10 8 2 2 1 2 2 2 1 0 1 ・・・ 2 0 1 2 1 存在しない 2 2 0 1 24 直並列グラフ 普通の点彩色数 補題1. 最大重み だけを計算すればよい 25 厳密アルゴリズム 直並列グラフ 条件 (a) 満たす (b) (c) for 満たさない 26 厳密アルゴリズム（並列接続） 直並列グラフ （並列接続） 時間 27 厳密アルゴリズム（直列接続） 直並列グラフ （直列接続） 時間 28 時間計算量 並列接続 時間 直列接続 時間 の個数 が多項式ならば の計算 直列接続または も多項式 並列接続の回数 29 グラフの帯域幅連続多重彩色( 彩色) 1. 彩色の基本的な性質 2. 直並列グラフに対する擬多項式時間厳密アルゴリズム : 点数 3. 直並列グラフに対する近似アルゴリズム，FPTAS : 任意の誤差率 4. 部分 -木への拡張 5. 結論 30 FPTAS FPTAS(Fully Polynomial-Time Approximation Scheme) 2 任意のグラフ 近似誤差率 を任意に選択 縮尺率 を適切に決める 正整数 新しい重み 時間計算量 が直並列グラフならば の最適解 1 1 新しい最大重み 重み 1 3 1 1 2 4 2 7 2 4 1 6 なる 6 の 彩色(近似解) 2 2 2 1 7 4 2 近似解 であることを次に示す 31 12 補題4. 証明． 任意のグラフ 近似解 最適解 が最小になる の無閉路向き付け の最長路 誤差 高々 誤差 高々 誤差 高々 □ 最長路長が最小になる の無閉路向き付け 近似解 33 定理． グラフのクラス に対し， 彩色問題を， と に関する多項式時間 で解く厳密アルゴリズムがあるならば，クラス に対してFPTASが存在する． 直並列グラフに対し， 彩色問題を と で解く厳密アルゴリズムがあるので， に関する多項式時間 定理より， 系1． 直並列グラフの 彩色問題に対してFPTASが存在する． その時間計算量は 34 グラフの帯域幅連続多重彩色( 彩色) 1. 彩色の基本的な性質 2. 直並列グラフに対する擬多項式時間厳密アルゴリズム : 点数 3. 直並列グラフに対する近似アルゴリズム，FPTAS : 任意の誤差率 4. 部分 -木への拡張 5. 結論 35 部分 -木 端子が +1個 ・・・ 補題1. なる 彩色 の最小スパン だけを計算すればよい 36 時間計算量 接続 時間 の計算 の個数 接続の回数 擬多項式時間 厳密アルゴリズム 37 定理． グラフのクラス に対し， 彩色問題を， と に関する多項式時間 で解く厳密アルゴリズムがあるならば，クラス に対してFPTASが存在する． 部分 -木に対し， 彩色問題を と に関する多項式時間 で解く厳密アルゴリズムがあるので， 定理より， 系2． 部分 -木の 彩色問題に対してFPTASが存在する． その時間計算量は 38 グラフの帯域幅連続多重彩色( 彩色) 1. 彩色の基本的な性質 2. 直並列グラフに対する擬多項式時間厳密アルゴリズム : 点数 3. 直並列グラフに対する近似アルゴリズム，FPTAS : 任意の誤差率 4. 部分 -木への拡張 5. 結論 39 結論 点彩色 多重彩色 帯域幅彩色 帯域幅連続 多重彩色 (b彩色) 木 直並列グラフ (部分2木) P P P P [ZN’04] P O(n) [AP’89] ? 擬多項式時間 厳密アルゴリズム FPTAS 部分3木 部分k木 一般のグラフ P P NPC P P [INZ’03] NPC NPC NPC [MR’03] FPTAS NPC NPC FPTAS 本文 NPC NPC 40 今後の課題 などの改善 41 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 43 彩色 の簡単な表現 条件 (a) (b) (c) for 44 彩色 の簡単な表現 (c) for 正 条件(2)を満たす 45 1．基本的な性質 補題1. どんな重み付きグラフ に対しても， 最大重み 普通の彩色数 色1 証明. の部分集合 独立 色2 色 独立 独立 は 彩色 独立 色3 46 1．基本的な性質 二部グラフや木に対しては線形時間で最適な 彩色が求まる 補題2. を二部グラフまたは木とし， とする．この時， 証明. 彩色 は自明 を証明する の部分集合 の部分集合 の証明 ：最適な 彩色， 6 の向き付け 2 1 for 2 2 は無閉路的 3 1 0 1 閉路があるならば 閉路はない 48 2 1 の証明 2 2 1 0 なる無閉路的向き付け において へ行く最長 有向道の長さ 6 条件 2 1 (a) 2 (b) (c) 2 3 のとき 非負 0 1 1 正 49 2 1 の証明 2 2 1 0 なる無閉路的向き付け において へ行く最長 有向道の長さ 6 条件 2 1 (a) 2 (b) (c) 2 3 のとき 非負 0 1 1 正 なので矛盾 逆向き 50 直並列グラフ 直並列グラフ 直並列グラフ 直並列グラフ（直列接続） 直並列グラフ（並列接続） 51 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 52 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 53 12 補題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 54 の証明 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 □ 55 任意のグラフ 補題4. 近似解 最適解 証明． が最小になる の無閉路向き付け の最長路 誤差 高々 補題３より 両辺に 56 上の式 の最長路 誤差 高々 証明は省略するが 誤差 高々 両辺に 誤差 高々 補題3より 両辺に 両辺に □ 最長路が最小になる 57 の向き付け -木の再帰的定義 1. 点からなる完全グラフは 木である． -木 2. が 木であり，その 点が完全グラフを誘導するとき，新しい１点を追加し， それら 点と辺で結んで得られるグラフも 木である． -木 -木 58 3-木 1. 点からなる完全グラフは 木である． 3-木 2. が 木であり，その 点が完全グラフを誘導するとき，新しい１点を追加し， それら 点と辺で結んで得られるグラフも 木である． 3-木 59 部分 -木 部分 -木: -木の部分グラフ 3-木 部分3-木 60 分解木 部分3-木 分解木 61 分解木 ・・・ ・・・ 分解木 62 部分 -木 ・・・ 補題1. なる 彩色 の最小スパン だけを計算すればよい 63 アルゴリズム ・・・ ・・・ 64 3-木 1. 点からなる完全グラフは 木である． 3-木 2. が 木であり，その 点が完全グラフを誘導するとき，新しい１点を追加し， それら 点と辺で結んで得られるグラフも 木である． 3-木 65
© Copyright 2024 ExpyDoc
