アルゴリズム，応用グラフ理論，グラフ描画 西関　隆夫 東北大学　大学院情報科学研究科

自己紹介 東北大学工学部通信工学科 　　「PCMパルス波形，FFT」 同　　電気及通信工学修士修了 　　「集中定数回路網合成に関する研究」 同　　博士修了 　　「回路網接続の位相幾何学的研究」 同　　工学部通信工学科　助手 　　グラフ理論，アルゴリズム 同　　助教授 　　線形時間アルゴリズム、グラフ描画、VLSIレイアウト Carnegie-Mellon 大学数学科客員研究員 　　東北大学工学部通信工学科　教授 同　　情報科学研究科　教授 同　　副研究科長、教育研究評議員 1969 1971 1974 1976 1977-78 1988 1993 2005

アルゴリズミカ，コンビナトリカ等の一流雑誌を含め，このような学術誌に合計28編の論文を発表しました．現在２編が投稿中です．

グラフ描画 ・・・ 様々の理論的な結果 様々な問題に対し効率のよい 辺素な道問題や グラフ分割問題 アルゴリズム 応用グラフ理論 計算理論 分解 近似 逐次 彩色 NP完全 近似困難 ・・・ 並列 ・・・ グラフ描画 VLSI設計 周暁です．本日は研究内容を紹介する，このような機会を設けていただき，有難うございます． いままで行った研究の内容と今後の課題について説明させていただきます．今までの研究内容は主に三つに分けられます． １つ目はアルゴリズムです． ２つ目は応用グラフ理論や計算理論です． ３つ目はグラフ描画です． アルゴリズムに関しては，様々な問題に対し効率のよい近似アルゴリズムや，逐次アルゴリズムや並列アルゴリズムなどを研究開発しました． 応用グラフ理論に関しては，グラフの彩色や分解などに関する様々の理論的な結果を得ました． また，計算理論に関しては，辺素な道問題がNP-完全であったり，グラフ分割問題が近似困難であることを示しました． グラフ描画に関しては，VLSI設計，特に配線によく応用される直交描画で，辺の折れ曲り最小なものを求めるアルゴリズムなどを与えました． これまでに，この三つの主な研究分野で， 直交描画 ・・・ 可視化

発表の流れ 研究内容の概要 主な研究テーマの紹介 今後の研究課題 きょうの発表の流れは，まず研究内容の概要を説明し，次に主な研究テーマを紹介し，最後に今後の研究課題を話します． まず研究内容の概要について紹介させていただきます．

グラフ描画 アルゴリズム 応用グラフ理論 計算理論 平面グラフのアルゴリズムと理論 グラフ彩色に関するアルゴリズム 研究内容の概要 平面グラフのアルゴリズムと理論 グラフ彩色に関するアルゴリズム アルゴリズム 応用グラフ理論 計算理論 辺素な道に関するアルゴリズム グラフ描画に関するアルゴリズム グラフ分割に関するアルゴリズム 並列アルゴリズム 近似アルゴリズム グラフ描画 最初はアルゴリズムの分野についての研究概要を話します． 主に以下のアルゴリズムを研究開発しました． １．まず，最初はグラフ彩色に関するアルゴリズムです．

平面グラフ 平面埋め込み，描画，5点彩色，辺素な道，多重フロー，ハミルトン閉路問題等に対する線形時間アルゴリズム 研究内容の概要 1 17 18 20 3 2 8 15 11 4 10 13 19 16 5 9 14 7 12 6 1 17 18 20 3 2 8 15 11 4 10 13 19 16 5 9 14 7 12 6 グラフ　　　　　　　　　　　　　　　　平面描画 平面埋め込み，描画，5点彩色，辺素な道，多重フロー，ハミルトン閉路問題等に対する線形時間アルゴリズム グラフ彩色は数百年以上に渡って，世界中の研究者によって研究されています． 例えば，地図彩色はそのなかの１つです．このようにすべての領域を彩色し，境界線を共有している２つの領域は異なる色にします．これは地図彩色と呼ばれています． このように東北の地図は海も含めて４色で彩色できます． 県や海をグラフの点に，境界線をグラフの辺に対応させますと，このようなグラフを得ることができます． 県の色を対応する点の色にすると，グラフの点彩色が得られます． 即ち，このようなグラフの点を最小色数で彩色すれば，最小色数の地図彩色が得られます． PQ-tree, JCSS, ’85

Kuratowskiの定理 平面グラフ K5, K3,3を含まない K5 K3,3 研究内容の概要 グラフ彩色は数百年以上に渡って，世界中の研究者によって研究されています． 例えば，地図彩色はそのなかの１つです．このようにすべての領域を彩色し，境界線を共有している２つの領域は異なる色にします．これは地図彩色と呼ばれています． このように東北の地図は海も含めて４色で彩色できます． 県や海をグラフの点に，境界線をグラフの辺に対応させますと，このようなグラフを得ることができます． 県の色を対応する点の色にすると，グラフの点彩色が得られます． 即ち，このようなグラフの点を最小色数で彩色すれば，最小色数の地図彩色が得られます． K5　　　　　　　　　　K3,3

博士論文 3端子直並列縦続グラフ を含まない 研究内容の概要 グラフ彩色は数百年以上に渡って，世界中の研究者によって研究されています． 例えば，地図彩色はそのなかの１つです．このようにすべての領域を彩色し，境界線を共有している２つの領域は異なる色にします．これは地図彩色と呼ばれています． このように東北の地図は海も含めて４色で彩色できます． 県や海をグラフの点に，境界線をグラフの辺に対応させますと，このようなグラフを得ることができます． 県の色を対応する点の色にすると，グラフの点彩色が得られます． 即ち，このようなグラフの点を最小色数で彩色すれば，最小色数の地図彩色が得られます．

平面グラフのアルゴリズムと理論 グラフ彩色に関するアルゴリズム アルゴリズム 研究内容の概要 最初はアルゴリズムの分野についての研究概要を話します． 主に以下のアルゴリズムを研究開発しました． １．まず，最初はグラフ彩色に関するアルゴリズムです．

地図彩色 点彩色 線形5-点彩色アルゴリズム[J. Algorithms 1981] 研究内容の概要 県や海をグラフの点に，境界線をグラフの辺に対応させる。 グラフの点を最小色数で彩色すれば，最小色数の地図彩色が得られる。 県や海の色を対応する点の色にする 点彩色 すべての領域を彩色し，境界線を共有している２つの領域は異なる色にする。 東北の地図は海も含めて４色で彩色できる。 4色 4色 グラフ彩色は数百年以上に渡って，世界中の研究者によって研究されています． 例えば，地図彩色はそのなかの１つです．このようにすべての領域を彩色し，境界線を共有している２つの領域は異なる色にします．これは地図彩色と呼ばれています． このように東北の地図は海も含めて４色で彩色できます． 県や海をグラフの点に，境界線をグラフの辺に対応させますと，このようなグラフを得ることができます． 県の色を対応する点の色にすると，グラフの点彩色が得られます． 即ち，このようなグラフの点を最小色数で彩色すれば，最小色数の地図彩色が得られます． 線形5-点彩色アルゴリズム[J. Algorithms 1981]

辺彩色 時間帯： ５色 辺彩色 ファイル転送問題 色数 ファイル転送時間 1時間目 2時間目 3時間目 4時間目 5時間目 file 1

平面グラフのアルゴリズムと理論 グラフ彩色に関するアルゴリズム 点彩色 辺彩色 全彩色 多重彩色 リスト彩色 アルゴリズム 研究内容の概要 また，点彩色のほかに，グラフの辺を彩色する辺彩色や，グラフの点と辺の両方を彩色する全彩色などがあります．また，点彩色や辺彩色や全彩色を一般化した多重彩色やリスト彩色に関するアルゴリズムを研究開発しました．

平面グラフのアルゴリズムと理論 グラフ彩色に関するアルゴリズム 辺素な道に関するアルゴリズム 入力 出力 アルゴリズム 研究内容の概要 次に扱ったのは辺素な道に関するアルゴリズムです． 与えられたグラフに幾つかの端子対が与えられているとします．この例では，青，赤，緑の３つの端子対が与えられています．このように，青い端子対を結ぶ道，赤い端子対を結ぶ道，緑の端子対を結ぶ道で，互い共通辺を持たない道を求めるアルゴリズムです． 入力 出力

配線層を２つ用いる２層配線では，水平配線は１層目に，垂直配線は２層目に置かれる。 グラフの辺は水平線分と垂直線分からなる折れ線で描かれる 研究内容の概要 配線層を２つ用いる２層配線では，水平配線は１層目に，垂直配線は２層目に置かれる。 グラフの辺は水平線分と垂直線分からなる折れ線で描かれる 折れ曲りが最小な直交描画を見つける線形時間アルゴリズムを与えた。 アルゴリズム VLSI 配線 グラフ彩色に関するアルゴリズム 折れ曲りがない 辺素な道に関するアルゴリズム グラフ描画に関するアルゴリズム 7個のピンを結ぶ配線 次はグラフ描画に関するアルゴリズムです． これはVLSI配線によく応用されます．このような7個のピンを結ぶ配線を表すグラフを考えましょう．配線層を２つ用いる２層配線では，水平配線は１層目に，垂直配線は２層目に置かれるので，２層配線は，このような直交描画に対応します．したがい，グラフの辺は水平線分と垂直線分からなる折れ線で描かれます．水平から垂直，あるいは垂直か水平に変わる部分は折れ曲りと呼ばれます．この例では，ここに折れ曲がりが1個ありますが，この緑のピンの配置を変えることによって，折れ曲りが全然ない描画が得られます．この研究では，このように折れ曲りが最小な直交描画を見つける線形時間アルゴリズムを与えました． 平面グラフ 折れ曲り 直交描画

4 6 5 3 2 10 7 8 12 15 13 25 どの負荷区間も１つの発電所からしか電力の供給を受けることができない。 研究内容の概要 どの負荷区間も１つの発電所からしか電力の供給を受けることができない。 電力を供給する発電所 電力を消費する学校や病院，住宅などの負荷区間 送電線のスイッチを閉じたり，開いたりして，このグラフをいくつかの連結成分に分割します。 負荷区間が必要とする電力量 電力網の配電計画を求めるアルゴリズムを与えた。 辺は送電線を表し，全ての送電線には開閉器，スイッチが付いている。 供給できる最大電力量 アルゴリズム グラフ彩色に関するアルゴリズム 辺素な道に関するアルゴリズム グラフ描画に関するアルゴリズム グラフ分割に関するアルゴリズム 合計：23 合計：13 合計：12 並列アルゴリズム 4 6 5 3 2 10 7 8 12 15 13 25 次はグラフ分割に関するアルゴリズムです． 例えば，四角の点が電力を供給する発電所とし，丸の点が電力を消費する学校や病院，住宅などの負荷区間とします．グラフの辺は送電線を表し，全ての送電線には開閉器，スイッチが付いています．四角い点内の数字はその発電所が供給できる最大電力量を表します．丸の点にある数字はその負荷区間が必要とする電力量です．どの負荷区間も１つの発電所からしか電力の供給を受けることができません．即ち，２つ以上の発電所からは電力の供給を受けることができません．そこで，送電線のスイッチを閉じたり，開いたりして，このグラフをいくつかの連結成分に分割します．無論，各連結成分には，電力を供給する点がちょうど一つあり，その供給電力は，その成分にある丸い点，即ち需要点の電力量の合計以上でないといけません．例えば，この黄色の連結成分を見てみましょう．四角い供給点は一つですし，その供給電力量２５は，４たす６たす５たす８の合計２３以上です．青色や緑色や茶色の連結成分でも同じです．このように，グラフを分割する，即ち電力網の配電計画を求めるアルゴリズムを与えました． また，そのほかに，並列アルゴリズムや近似アルゴリズムも研究開発しました． 近似アルゴリズム

描画 入力 出力 点彩色 辺彩色 全彩色

グラフ全体(任意のk) 部分k木（k=定数) 直並列グラフ（k=2) 木 (k=1) 平面グラフ 描画

直交描画 直交描画 直交描画

合計：23 合計：13 合計：12 4 6 5 3 2 10 7 8 12 15 13 25 4 6 5 3 2 10 7 8 12 15 13 25 合計：23 合計：13 合計：12

グラフ描画 アルゴリズム 応用グラフ理論 計算理論 彩色問題 色々な彩色について，彩色できるため 研究内容の概要 辺彩色 最大次数 Δ ＝３ 彩色問題 一般グラフに対し、 Δ ＋１個の色 で辺彩色可能　　　　　　　[Vizing 1965] アルゴリズム 応用グラフ理論 計算理論 最小色数の上界 直並列グラフ（ｋ=2）や部分ｋ木（ｋ端子）： Δ≧２ｋであるならば、 Δ色で辺彩色可能 グラフ描画 次に応用グラフ理論や計算理論の分野についての研究概要を話します． １．まず，最初に彩色問題です． 　　色々な彩色について，彩色できるための色数の上界を求めました．点に接続している辺の本数を次数といいます．この点は2次で，この点は3次です．このグラフの最大次数Deltaは３です．例えば，一般のグラフを辺彩色するには，最大次数Delta以上の色がどうしても必要です．即ちDeltaは辺彩色数の下界です．これに対し，Delta＋１色で彩色可能であることが，既に知られていました．このように直列接続と並列接続を繰り返して得られたグラフを直並列グラフといいます．直並列グラフを一般化したものは部分ｋ木と呼ばれます．ｋ＝２の部分ｋ木が直並列グラフです．木，直並列グラフ，部分ｋ木，グラフ全体はこのような関係です．部分ｋ木に対しては，もし，最大次数Deltaが２ｋ以上であるならば，部分ｋ木は最小色数のDelta色で辺彩色可能であることを証明しました．無論，Delta-1色では彩色できないので，これは最良です．これは，純粋にグラフ理論の結果です． また，辺彩色の一般化であるｆ彩色や[g,f]彩色などについても同様な上界をもとめることに成功しました． 色々な彩色について，彩色できるため グラフ全体(任意のk) 部分k木（k=定数) 直並列グラフ（k=2) 木 (k=1) 一般のグラフを辺彩色するには，最大次数Δ以上の色がどうしても必要です。 点に接続している辺の本数を次数という。 辺彩色の一般化であるｆ-彩色、[g,f]-彩色 などについても同様な上界を求めることに 成功した。 直並列グラフ 部分３木グラフ =3端子直並列グラフ

Σ Gi Δ （Gi ） Δ （ Gi ） 分解 ≦３ｋ ２ｋ≦ 辺彩色 ＝ Δ （ G ） i 辺集合をいくつかの部分集合に分解する。 研究内容の概要 Δ （Gi ） ≦３ｋ ２ｋ≦ 辺彩色 Δ （ Gi ） Σ ＝ Δ （ G ） i Gi 最大次数Δが大きいとき 辺集合をいくつかの部分集合に分解する。 また，部分ｋ木において，辺集合をいくつかの部分集合に分解し，各部分辺集合から誘導される部分グラフGiについて，最大次数が２ｋ以上で３ｋ以下であり，部分グラフの最大次数の合計は元のグラフGの最大次数に等しくなるように，分割できることを示しました．この分解は部分ｋ木を線形時間で辺彩色するアルゴリズムに応用できます． 部分ｋ木G

木に対しては，同じ色の端子間の道は１本しかない 応用グラフ理論 研究内容の概要 木（ｋ=1）： 多項式時間で解ける 既知 計算理論 彩色問題 研究成果 辺素な道問題 直並列グラフ（ｋ=2）： NP-完全 グラフ全体(任意のk) 部分k木（k=定数) 直並列グラフ（k=2) 　　木 　　 　(k=1) 部分ｋ木： 端子の配置がある条件を 満たしたとき 多項式時間で解ける 木に対しては，同じ色の端子間の道は１本しかない 次は辺素な道問題です． このような閉路のないグラフ，即ち，木に対しては，同じ色の端子間の道は１本しかないので，多項式時間で辺素な道を簡単に見つけられます．一方，木より少しだけ広いクラスである直並列グラフに対しは，辺素な道を見つける問題がNP-完全であることを証明しました．従って，P=NPではない限り，多項式時間アルゴリズムが存在しそうもないことを証明しました．木に対し多項式時間で解けて，直並列グラフに対しNP困難である自然な問題はいままで知られていなかったので，辺素な道はそのような問題であることが分かった最初の問題です． 部分ｋ木に対し，もし端子の配置がある条件を満たしたとき，辺素な道を多項式時間で見つけるアルゴリズムを与えました． 入力 出力 木に対し多項式時間で解けて，直並列グラフに対しNP困難である自然な問題はいままで知られていなかった

研究成果 NP困難 木： 近似可能（FPTAS) 彩色問題 辺素な道問題 一般グラフ： 極めてよい近似アルゴリズム 応用グラフ理論 研究内容の概要 研究成果 (計算量理論) NP困難 近似可能（FPTAS) 木： 彩色問題 辺素な道問題 一般グラフ： 近似困難（MAX SNP-hard） 極めてよい近似アルゴリズム グラフ分割問題 合計：23 合計：13 合計：12 P=NPでない限り，近似アルゴリズムすら存在しそうもない 次に，先に紹介したグラフ分割問題について詳しく述べます． グラフ分割問題は木に対してすらNP困難であることを証明しました．また，FPTASという極めてよい近似アルゴリズムを与えることによって，近似可能であることを証明しました．さらに，一般のグラフに対し，MAX SNP-Hardであり，P=NPでない限り，近似アルゴリズムすら存在しそうもないことを証明しました． 4 6 5 3 2 10 7 8 12 15 13 25

グラフ描画 etc… グラフをできるだけ“見やすく”描画したい 応用により要求される “見やすさ”が異なる 様々な描画法 凸描画 格子凸描画 矩形勢力描画 etc…

グラフ描画 アルゴリズム 応用グラフ理論 計算理論 グラフ描画 本研究では，最小折れ曲りの直交描画を見つけるアルゴリズムを研究開発した。 研究内容の概要 直交描画 bend 折れ 曲り 個数： ４ グラフ描画 アルゴリズム 応用グラフ理論 計算理論 本研究では，最小折れ曲りの直交描画を見つけるアルゴリズムを研究開発した。 最大次数が3以下の直並列グラフGが与えられたときに、 Gの直交描画で折れ曲がりの個数が最小なものを線形時間で 見つけるアルゴリズムを与えた。 直交描画はよくVLSI 二層配線に応用される。 グラフ描画 折れ曲り　　　ビアホール 　　　　　　　　スルーホール VLSI 設計 平面グラフを交差なしで，辺を水平線分と垂直線分で描画する。 ３つ目のグラフ描画については，主に直交描画について研究開発を行いました． 直交描画というのは，平面グラフを交差なしで，辺を水平線分と垂直線分で描画することです．点以外のところでの水平線分と垂直線分の交点は折れ曲がり（bend）といいます．これはこのグラフの直交描画の一例で，折れ曲がり個数が4個です．前にも述べたように，直交描画はよくＶＬＳＩ2層配線に応用されます．例えば，水平線分を１層目に，垂直線分を２層目に配置します．黒い縦線はスルーホールやビアになります．スルーホールやビアはコストがかかりますので，スルーホールの個数を最小にしたい訳です．この描画では，４つのスルーホールがあります．本研究では，最小折れ曲がりの直交描画を見つけるアルゴリズムを研究開発しました．研究成果としては，最大次数が3以下の直並列グラフＧが与えられたときに，Ｇの直交描画で折れ曲がりの個数が最小なものを線形時間で見つけるアルゴリズムを与えました． 点以外のところでの水平線分と垂直線分の交点は折れ曲がり（bend）という。 最小にしたい

折れ 曲り 個数： ４ 直交描画

合計：17 20 4 4 合計： 5 4 4 10 8 8 6 6 5 5 3 3 5 5 合計：12 15 7 7 6 6 2 2 10 10 13 4 6 5 3 2 10 7 8 15 13 20 合計：19

4 6 5 3 2 10 7 8 12 15 13 25 4 6 5 3 2 10 7 8 12 15 13 25 4 6 5 3 2 10 7 8 15 13 20 合計：19

発表の流れ グラフ描画 研究内容の概要 主な研究テーマの紹介 今後の研究課題 応用グラフ理論 計算理論 アルゴリズム 以上で研究内容の概要の紹介が終わりました．次に主な３つの具体的な研究テーマについて紹介します． 便宜上これら３つに分類しましたが，個々の研究テーマはこれら３つのいくつにまたがります． 便宜上これら３つに分類しましたが，個々の研究テーマはこれら３つのいくつにまたがります。

グラフ描画 主な研究テーマの紹介 応用グラフ理論 計算理論 アルゴリズム グラフ分割 グラフ描画 グラフ彩色 グラフ 辺彩色 直交描画 4 6 5 3 2 10 7 8 12 15 13 25 直交描画 グラフ描画 グラフ描画 応用グラフ理論 計算理論 アルゴリズム グラフ彩色 １つ目はグラフ分割です． ２つ目はグラフ描画です． ３つ目はグラフ彩色です．

主な研究テーマの紹介 グラフ分割 グラフ直交描画 グラフ彩色 ＮＰ困難 近似困難 近似 応用グラフ理論 計算理論 アルゴリズム 4 6 5 3 2 10 7 8 12 15 13 25 4 6 5 3 2 10 7 8 12 15 13 25 グラフ分割 グラフ直交描画 グラフ彩色 近似 まずグラフ分割について説明します． ＮＰ困難 応用グラフ理論 計算理論 アルゴリズム 近似困難

電力網 フィーダ 負荷区間 電力を消費する病院や学校や住宅などの負荷区間を丸で表す。 電力を供給するフィーダを四角で表す。 主な研究テーマの紹介 電力網 フィーダ 負荷区間 このような電力網を考えましょう．電力を供給するフィーダを四角で表しています．丸は電力を消費する病院や学校や住宅などの負荷区間を表しています． 電力を消費する病院や学校や住宅などの負荷区間を丸で表す。 電力を供給するフィーダを四角で表す。

電力網 フィーダ 負荷区間 送電線の開閉器 オレンジのフィーダは電力をオレンジの負荷区間に送っている。 主な研究テーマの紹介 これが送電線の開閉器です．この開閉器を閉じることによって，この負荷区間にこのフィーダから電力を供給しています．同様にこの負荷区間はこのフィーダから電力が供給されます．このフィーダは電力をオレンジの負荷区間に送っています． オレンジのフィーダは電力をオレンジの負荷区間に送っている。

電力網 停電 開いている状態のスイッチを消す。 各連結成分にちょうど１つ供給点 故障 フィーダ 負荷区間 主な研究テーマの紹介 開いている状態のスイッチを消す。 電力網 各連結成分にちょうど１つ供給点 故障 フィーダ 負荷区間 停電 同様に赤いフィーダは電力を赤い負荷区間に送っています．緑のフィーダも同じです． 見やすくするために，開いている状態のスイッチを消しますと，３つの連結成分，赤，黄色，緑の成分に分割されています．各連結成分にちょうど１つ供給点があります．先程，消した開閉器を戻します．もしこの負荷区間に故障が起きた場合に，これから先の負荷区間は停電になってしまいます． 赤いフィーダは電力を赤い負荷区間に送っている。 緑のフィーダは電力を緑の負荷区間に送っている。

例 The New York City Blackout(2003) 東京大停電（２００６） 主な研究テーマの紹介 例えば，2003年にニューヨークの大停電や，昨年に東京大停電がありました．

電力網 一刻も早く復旧させたい フィーダ 負荷区間 周りで余っていた電力を停電区間に送ります． 開閉器をON-OFFしなおす 主な研究テーマの紹介 一刻も早く復旧させたい 電力網 フィーダ 負荷区間 周りで余っていた電力を停電区間に送ります． そのとき，一刻も早く復旧させることが望まれます． その方法としては，このように開閉器をON-OFFしなおすことによって，周りで余っていた電力を停電区間に送ります． 開閉器をON-OFFしなおす

電力網 フィーダ 負荷区間

電力網 フィーダ 負荷区間

電力網 フィーダ 負荷区間

電力網 フィーダ 負荷区間

電力網 フィーダ 負荷区間

電力網 フィーダ 負荷区間

電力網 フィーダ 負荷区間 故障

初めに 現在の電力網において 余力の送り方により復旧の程度が変わる 東京大停電 2006年8月14日8:17~10:44 停電区間

グラフを用いて定式化 よい送り方を見つけることに成功した 現在の電力網において 余った電力の送り方により復旧方法： 主な研究テーマの紹介 現在の電力網において 余った電力の送り方により復旧方法： 現在はオペレータの経験則に基づき復旧 ・時間がかかり過ぎる ・余力の良い送り方がなかなか見つけられない 現状では，オペレータの経験則により復旧していましたので， あまりに時間がかかりすぎです．また，人手ではよい送り方がなかなか見つけられない訳です．本研究では，グラフを用いて定式化し，よい送り方を見つけることに成功しました．これについて，詳しく説明したいと思います． グラフを用いて定式化 よい送り方を見つけることに成功した

グラフ グラフ 5 10 20 5 10 10 50 5 4 40 2 5 4 3 3 15 3 3 10 3 需要点 供給点

グラフ グラフ 合計：20 合計：40 5 10 20 5 10 10 50 5 4 40 合計：35 2 5 4 3 3 15 3 3 10 3 需要点 供給点

グラフ グラフ 故障 合計：20 合計：40 50 10 5 2 15 3 4 10 3 20 3 4 5 40 合計：35 需要点 供給点

グラフ グラフ 50 10 5 2 15 3 4 10 3 20 5 5 40 4 3 3 需要点 供給点 故障 合計：5 合計：40 合計：35 4 3 3 需要点 供給点

グラフ グラフ 5 10 20 5 10 10 50 5 4 40 2 5 4 3 3 15 3 3 10 3 需要点 供給点

グラフ 供給点 と需要点 供給点 需要点 グラフの点が2種類ある。 主な研究テーマの紹介 グラフの点が2種類あり，四角で表している供給点と丸で表している需要点です． 供給点 需要点

主な研究テーマの紹介 グラフ グラフの辺は開閉器がある送電線を表す。 開閉器 供給量 12 15 13 25 4 6 5 3 2 10 7 8 需要量 グラフの辺は開閉器がある送電線を表しています． 各供給点には供給できる供給量が与えられており，各需要点には需要量が与えられています． 供給点 需要点

次の条件 (a) , (b) を満たすようにグラフを分割する． 主な研究テーマの紹介 分割 次の条件 (a) , (b) を満たすようにグラフを分割する． 4 6 25 4 6 5 3 2 10 7 8 12 　　次の条件（a）および（ｂ）を満たすようにグラフを分割します． 8 5 15 13

次の条件 (a) , (b) を満たすようにグラフを分割する． 主な研究テーマの紹介 分割 次の条件 (a) , (b) を満たすようにグラフを分割する． 4 6 5 3 2 10 7 8 12 15 13 25

次の条件 (a) , (b) を満たすようにグラフを分割する． 主な研究テーマの紹介 分割 次の条件 (a) , (b) を満たすようにグラフを分割する． スイッチが開いている送電線は灰色で描かれている。 (a) : 各連結成分はちょうど1つの供給点を含む． (b) : 供給点を含む連結成分において， 　　　その供給量が需要量の合計以上となる． 合計：23 合計：13 合計：12 25 4 6 5 3 2 10 7 8 4 6 5 3 2 10 7 8 12 条件（a）：各連結成分はちょうど１つの供給点を含まないといけません． 条件（ｂ）：連結成分において，その供給量は需要量の合計以上でないといけません． これは求めたい分割です．スイッチが開いている送電線は灰色で描かれています．各連結成分はちょうど１つの供給点を含み，その供給量は需要量の合計以上になっています． 15 13

その代わりに，次のような最大分割を求めます． 主な研究テーマの紹介 最大分割 分割 その代わりに，次のような最大分割を求めます． 需要量の合計：６０ 供給量の合計：５８ 分割が存在しない 4 6 5 3 2 10 7 8 15 13 20 しかし，条件を満たす分割が存在しない場合があります．例えば，この場合に需要量の合計は６０で，供給量の合計は５８ですので，明らかに求めたい分割は存在しません．その代わりに，次のような最大分割を求めます．

次の条件 (a) , (b) を満たすようにグラフを分割する． 主な研究テーマの紹介 最大分割 次の条件 (a) , (b) を満たすようにグラフを分割する． (a) : 各連結成分は高々1つの供給点を含む． (b) : 供給点を含む連結成分において， 　　　その供給量が需要量の合計以上となる． 供給点を含まない 20 4 6 5 3 2 10 7 8 4 6 5 3 2 10 7 8 10 条件（a）：各連結成分は高々１つの供給点を含まないといけません．即ち各連結成分は供給点１個だけを含むか，あるいはこの成分のように全然含まないかのどちらかでないといけません． 条件（ｂ）：供給点を含む連結成分においては，無論，その供給量は需要量の合計以上でないといけません． 供給点１個だけを含む 15 13

次の条件 (a) , (b) を満たすようにグラフを分割する． 主な研究テーマの紹介 最大分割 充足量が最大となる分割を求めたい 次の条件 (a) , (b) を満たすようにグラフを分割する． (a) : 各連結成分は高々1つの供給点を含む． (b) : 供給点を含む連結成分において， 　　　その供給量が需要量の合計以上となる． 供給された電力量の合計 合計：17 合計：7 合計： 5 合計：12 20 4 6 5 3 2 10 7 8 4 6 5 3 2 10 7 8 10 条件（a），（ｂ）を満たす分割のうちで，充足量が最大となる分割，即ち供給された電力量の合計が最大となる分割を求めたい訳です． 15 13

主な研究テーマの紹介 最大分割 充足量が最大となる分割を求めたい この分割の充足量 17 + 5 + 12 + 7 = 41 合計：17 合計：7 合計： 5 合計：12 20 4 6 5 3 2 10 7 8 4 6 5 3 2 10 7 8 10 例えば，この分割の充足量は， この黄色の連結成分にある需要量の合計は１７， 青い連結成分にある需要量の合計は５， 茶色の連結成分にある需要量の合計は１２， 緑の連結成分にある需要量の合計は７ですので， それらを全部たすと４１です． 15 13

最大分割 停電量を最小にしたい この分割の充足量 19 + 8 + 12 + 15 = 54 最大充足量 20 4 6 5 3 2 10 7 主な研究テーマの紹介 最大分割 充足量が最大となる分割を求めたい 停電量を最小にしたい この分割の充足量 19 + 8 + 12 + 15 = 54 最大充足量 合計：19 合計：15 合計： 8 合計：12 20 4 6 5 3 2 10 7 8 4 6 5 3 2 10 7 8 10 一方，この分割の充足量は５４で，最大です．このような充足量が最大の分割を求めたい訳です．言い換えると，停電量を最小にしたいわけです． 15 6 13

分割問題の計算量 3 4 5 7 11 b = 13 最大部分集合和問題 集合 A 木 NP-困難 最大部分集合和問題(NP-困難) 主な研究テーマの紹介 分割問題の計算量 3 4 5 7 11 b = 13 最大部分集合和問題 (Knapsack問題の簡単化) 　 集合 A 木 7 4 3 6 2 9 5 15 25 NP-困難 この分割問題の計算量について説明いたします．木に対してすら，この最大分割問題はＮＰ－困難であることを証明しました．既にＮＰ－困難であることが分かっている問題，ここでは最大部分集合和問題と呼ばれるナップザック問題の簡単化したものを考えます．その入力は整数集合Ａと整数ｂです．出力は次の条件を満たすＡの部分集合Ｃです．Ｃの要素の合計はｂ以下でかつ最大になるようなＡの部分集合です．例えば，集合Ａが３，４，５，７，１１からなり，ナップザックの大きさｂが１３であるとき， 最大部分集合和問題(NP-困難) 入力: 整数集合 A と 整数 b 出力: A の部分集合C： 　　　　 Cの要素の合計はb以下かつ最大である。 木に対してすら，最大分割問題はＮＰ-困難であることを証明しました。 既にＮＰ-困難であることが分かっている問題

計算量 最大部分集合和問題 木 b = 13 C NP-困難 3 4 5 7 11 集合 A 最大部分集合和問題(NP-困難) 主な研究テーマの紹介 計算量 最大部分集合和問題 (Knapsack問題の簡単化) 木 7 4 3 6 2 9 5 15 25 b = 13 C NP-困難 3 4 5 7 11 集合 A 求めたい出力の部分集合Ｃは５と７からなります．Ｃの要素の合計は１２で，ナップザックの大きさｂ＝１３より小さいです．合計が１３になるような部分集合が存在しませんので，Ｃが最大です．明らかに，最大部分集合和問題は最大分割問題の極めて特殊な場合，つまり，グラフがスターであり，しかも供給点が１つしかなく，木の中心にある場合です．よって，最大分割問題は木に対してすらＮＰ－困難です．それでは，“よい近似アルゴリズムは存在するのか？”という疑問がわきます． 最大部分集合和問題(NP-困難) 入力: 整数集合 A と 整数 b 出力: A の部分集合C ：. 　　　　 Cの要素の合計はb以下かつ最大である。 明らかに，最大部分集合和問題は最大分割問題の極めて特殊な場合 グラフがスターであり，しかも供給点が１つしかなく，木の中心にある場合です。 よい近似アルゴリズムは存在するのか？

関連結果 最大部分集合和問題 完全近似スキーム Fully Polynomial-Time Approximation Scheme 主な研究テーマの紹介 関連結果 最大部分集合和問題 完全近似スキーム Fully Polynomial-Time Approximation Scheme (FPTAS) [Ibarra and Kim ’75] 3 4 5 7 11 13 　　70年代に最大部分集合和問題に対しては完全近似スキームＦＰＴＡＳというよい近似アルゴリズムがあることがすでに知られていました．完全近似スキームＦＰＴＡＳというのは０から１の間の任意のeに対し，問題の入力サイズnと１/ eの多項式時間で，最適解OPTの (１－e)倍以上の近似解Approを見つけるアルゴリズムです． 完全近似スキーム（FPTAS）: 任意のe（0 < e < 1）に対し, n と 1/ e の多項式時間で APPRO > (1–e ) OPT を満たす近似解APPROを見つけるアルゴリズム 極めてよい近似アルゴリズム

? 関連結果 最大部分集合和問題 完全近似スキーム Fully Polynomial-Time Approximation Scheme 主な研究テーマの紹介 関連結果 最大部分集合和問題 完全近似スキーム Fully Polynomial-Time Approximation Scheme (FPTAS) [Ibarra and Kim ’75] 3 4 5 7 11 13 最大分割問題 の特殊な場合 研究成果 しかし，一般グラフに対し，最大分割を見つけるいい近似アルゴリズムが存在しそうにないことを証明しました．即ち最大分割問題は一般グラフに対しMAXSNP-hardであり,Ｐ＝ＮＰではない限り，ＰＴＡＳは存在しそうにないことを示しました． 7 4 3 6 2 9 5 15 25 ∃FPTAS 4 6 5 3 2 10 7 8 12 15 13 25 近似困難 一般グラフのクラス に対し、いい近似 アルゴリズム ? MAXSNP-困難

? 関連結果 最大部分集合和問題 完全近似スキーム Fully Polynomial-Time Approximation Scheme 主な研究テーマの紹介 関連結果 最大部分集合和問題 完全近似スキーム Fully Polynomial-Time Approximation Scheme (FPTAS) [Ibarra and Kim ’75] 3 4 5 7 11 13 最大分割問題 の特殊な場合 最大部分集合和問題は我々の最大分割問題の特殊の場合ですので，一般グラフのグラスに対しも，いい近似アルゴリズムが存在するかと予想されます． しかし，一般グラフに対し，最大分割を見つけるいい近似アルゴリズムが存在しそうにないことを証明しました．即ち最大分割問題は一般グラフに対しMAXSNP-hardであり,Ｐ＝ＮＰではない限り，ＰＴＡＳは存在しそうにないことを示しました． 一般グラフのクラス に対し、いい近似 アルゴリズム ? 予想

研究成果（最大分割問題） 一般のグラフ (1) MAXSNP-困難 (近似困難) P=NP ではない限り、 PTASが存在しない 主な研究テーマの紹介 研究成果（最大分割問題） 一般のグラフ (1) MAXSNP-困難 (近似困難) 4 6 5 3 2 10 7 8 12 15 13 25 P=NP ではない限り、 PTASが存在しない P=NP ではない限り、 FPTASも存在しない 最大分割を見つけるいい近似アルゴリズムが存在しそうもないことを証明しました． しかし，一般グラフに対し，最大分割を見つけるいい近似アルゴリズムが存在しそうにないことを証明しました．即ち最大分割問題は一般グラフに対しMAXSNP-hardであり,Ｐ＝ＮＰではない限り，ＰＴＡＳは存在しそうにないことを示しました． ＰＴＡＳ（近似スキーム）というのは，０から１の間の任意のeに対し，問題の入力サイズnの多項式時間で最適解の(１－e)倍以上の近似解Approを見つけるアルゴリズムです．ここで，１/ eは定数としています．もちろん，Ｐ＝ＮＰではない限り，ＦＰＴＡＳが存在しそうにないことになります． （1/e :定数） 近似スキーム（PTAS）: 任意のe（0 < e < 1）に対し, n の多項式時間で APPRO > (1–e ) OPT を満たす近似解APPROを見つけるアルゴリズム

研究成果（最大分割問題） 一般のグラフ (1) MAXSNP-困難 (近似困難) P=NP ではない限り、 PTASが存在しない 木 主な研究テーマの紹介 研究成果（最大分割問題） 一般のグラフ (1) MAXSNP-困難 (近似困難) 4 6 5 3 2 10 7 8 12 15 13 25 P=NP ではない限り、 PTASが存在しない 木 NP-困難 　次に，木に対しては最大分割問題はNP困難ですが，最大分割問題を解く完全近似スキームＦＰＴＡＳが存在することを示しました． 7 4 3 6 2 9 5 15 25 (2)完全近似スキーム 　　FPTAS

木T Tv Tv (2)完全近似スキーム （FPTAS） 3 9 v 5 10 20 5 20 10 3 9 5 9 5 v 3 5 20 主な研究テーマの紹介 (2)完全近似スキーム　（FPTAS） 木T Tv 3 9 v 5 10 20 部分木 Tvの最適な分割 木 Tの最適な分割 5 20 10 3 9 Tv 5 9 5 v 3 5 20 10 10 9 20 5 3 充足量 = 18 充足量 = 20

(2)完全近似スキーム （FPTAS） Tv Tv 動的計画法 5 9 3 20 10 v 充足量: 10 主な研究テーマの紹介 (2)完全近似スキーム　（FPTAS） 動的計画法 Tv 5 9 3 20 10 v 充足量: 10 20 - (10+5+3) = 2 余った力 Tv 5 9 5 10 20-10= v 3 5 20 10 10 9 20 5 3 充足量: 18

(2)完全近似スキーム （FPTAS） Tv Tv 動的計画法 5 9 3 20 10 v 充足量: 15 20-(10+3)= 7 主な研究テーマの紹介 (2)完全近似スキーム　（FPTAS） 動的計画法 5 9 Tv 3 20 10 v 充足量: 15 20-(10+3)= 7 20-(10+5)=5 Tv 5 9 5 v 10 10 9 20 20 5 5 3 3 充足量: 13

(2)完全近似スキーム （FPTAS） Tv 3 9 v 5 10 20 木 Tの最適な分割 5 9 Tv 3 20 10 v 主な研究テーマの紹介 (2)完全近似スキーム　（FPTAS） 5 9 Tv 3 20 10 v 充足量: 15 7 充足量: 13 充足量: 10 2 充足量: 18 Tv 3 9 v 5 10 20 木 Tの最適な分割

(2)完全近似スキーム （FPTAS） 階段, 非増加関数 動的計画法 余った電力量 F 充足量 F points FPTASのアイデア 主な研究テーマの紹介 (2)完全近似スキーム　（FPTAS） 階段,　非増加関数 動的計画法 FPTASのアイデア 1 2 3 余った電力量 5 9 Tv 3 20 10 v 充足量: 15 7 充足量: 13 充足量: 10 2 充足量: 18 各充足量の値ごとに根から外側に供給できる最大電力量を計算する そのFPTASのアイデアだけを紹介いたします．動的計画法を用いて，葉から根に向かって，各部分木において各充足量の値ごとに根から外側に供給できる最大電力，つまり，その値だけ充足させたときに余る最大の電力量を計算いたします．この余った電力量は，このような階段状の非増加関数になります．ここで，横軸は充足量で，縦軸は余った電力量です．このＦは供給点の供給量の合計です．明らかにＦ以上供給できません． F 1 2 3 充足量 F points

(2)完全近似スキーム （FPTAS） Tv Tv Tv 15 v 5 4 3 木 Tの最適な分割 5+4 = 9 足りない力 15 v 5 主な研究テーマの紹介 (2)完全近似スキーム　（FPTAS） Tv 15 v 5 4 3 木 Tの最適な分割 5+4 = 9 足りない力 Tv 15 v 5 4 3 5 Tv v 5 15 3 4 5 充足量: 9

(2)完全近似スキーム （FPTAS） Tv 15 v 5 4 3 木 Tの最適な分割 Tv 15 v 5 3 4 充足量: 8 8 主な研究テーマの紹介 (2)完全近似スキーム　（FPTAS） Tv 15 v 5 3 4 充足量: 8 8 充足量: 12 12 充足量: 9 9 充足量: 5 Tv 15 v 5 4 3 木 Tの最適な分割

(2)完全近似スキーム （FPTAS） 階段, 非減少関数 動的計画法 足りない電力量 F 充足量 F points FPTASのアイデア 階段,　非減少関数 動的計画法 FPTASのアイデア 1 2 3 足りない電力量 F 充足量 Tv 15 v 5 3 4 充足量: 8 8 充足量: 12 12 充足量: 9 9 充足量: 5 各充足量の値ごとにその充足量を達成するために外側からもらわないといけない最小電力量を計算する また，各部分木に充足量ごとに，その充足量を達成するために外側からもらわないといけない最小電力，つまり，足りない電力量を計算いたします．このような階段状の非減少関数になります． F points

主な研究テーマの紹介 (2)完全近似スキーム　（FPTAS） 余った電力量 F 1 2 3 充足量 足りない電力量 全体でO(F 2n) 時間 3 20 4 7 2 8 6 5 9 15 25 3 20 4 7 2 8 6 5 9 15 25 Fがnの多項式とは限りません。 厳密解 O(F 2) 時間 この部分木の余った電力量のＤＰ表と足りない電力量のＤＰ表，およびこの部分木のDP表から，２つの部分木を合わせた部分木のＤＰ表を求めることがＯ（Ｆ２）時間でできます．これを繰り返して木全体のDP表をO(F2n)時間で求めることができます．このままでは，厳密解が求まりますが，Fがｎの多項式とは限りませんので，計算時間はｎの指数関数になってしまいます． しかしこのアルゴリズムに基づいて， 余った電力量 F 1 2 3 充足量 足りない電力量 足りない電力量 F 1 2 3 充足量 余った電力量

(2)完全近似スキーム （FPTAS） F 根 3 20 4 7 2 8 6 5 9 15 25 動的計画法 最大充足量 余った力 主な研究テーマの紹介 (2)完全近似スキーム　（FPTAS） 余った力 F 1 2 3 充足量 足りない力 最大充足量 根 3 20 4 7 2 8 6 5 9 15 25 動的計画法

研究成果（最大分割問題） 一般のグラフ (1) MAXSNP-困難 (近似困難) P=NP ではない限り、 PTASが存在しない 木 主な研究テーマの紹介 研究成果（最大分割問題） 一般のグラフ (1) MAXSNP-困難 (近似困難) 4 6 5 3 2 10 7 8 12 15 13 25 P=NP ではない限り、 PTASが存在しない 木 NP-困難 最大分割を求める完全近似スキームＦＰＴＡＳを構成することができます． 7 4 3 6 2 9 5 15 25 (2)完全近似スキーム 　　FPTAS

主な研究テーマの紹介 研究成果（最大分割問題） 直並列グラフ (3)擬多項式時間 4 6 5 3 2 10 7 8 12 15 13 25

研究成果（最大分割問題） 明電舎との共同研究 配電融通システム 北海道電力に納入予定 特許申請中 約1時間 1秒以内 近似率：98%以上 主な研究テーマの紹介 環境 AMD Opteron Processor 252 (2.6GHz)×2 約1時間 明電舎との共同研究 200 150 250 地方都市規模の電力網 配電融通システム 1秒以内 近似率：98%以上 開発した 近似方法 　　北海道電力に納入予定 　　特許申請中 　明電舎との共同研究で，従来，地方都市規模の電力網で， 約１時間かかった計算を我々が開発した近似方法では1秒以内で，近似率が９８％以上での解を求めることに成功しました．この研究成果を組み込んだ配電融通システムを北海道電力に納入予定で，また，この研究成果の特許も申請中です．

主な研究テーマの紹介 グラフ分割 直交描画 グラフ直交描画 グラフ彩色 応用グラフ理論 アルゴリズム 近似 ＮＰ困難 近似困難

グラフ描画 以下の3つの主な研究テーマ 応用グラフ理論 計算理論 アルゴリズム グラフ分割 グラフ直交描画 グラフ彩色 直交描画 主な研究テーマの紹介 以下の3つの主な研究テーマ グラフ分割 直交描画 グラフ直交描画 グラフ描画 応用グラフ理論 計算理論 アルゴリズム グラフ彩色 次にグラフ描画のテーマについて紹介したいと思います．

主な研究テーマの紹介 直交描画 辺の交差がないように、辺を水平線分や垂直線分 の折れ線で描く 入力 出力 直交描画 平面グラフ

直交描画 bend 辺の交差がないように、辺を水平線分や垂直線分 の折れ線で描く 折れ曲り 入力 出力 折れ曲り：１ 直交描画 平面グラフ 主な研究テーマの紹介 直交描画 辺の交差がないように、辺を水平線分や垂直線分 の折れ線で描く 入力 出力 折れ曲り：１ 直交描画 bend 直交描画というのは，辺の交差がないように，辺を水平線分と垂直線分の折れ線で描きます．これがこのグラフの1つの直交描画です．ここは，折れ曲がりです． 平面グラフ 折れ曲り

直交描画 bend 辺の交差がないように、辺を水平線分や垂直線分 の列で描く VLSI 設計 折れ曲り 出力 折れ曲り：１ 主な研究テーマの紹介 直交描画 辺の交差がないように、辺を水平線分や垂直線分 の列で描く 折れ曲り　　　ビアホール 　　　　　　　　スルーホール VLSI 設計 出力 折れ曲り：１ 直交描画 bend この描画には，折れ曲がりが1個あり，それはＶＬＳＩのスルーホールなどと対応します．ですから，折れ曲がりの個数が最小な描画を求めたいわけです． 折れ曲り

直交描画 bend 違う平面埋め込み 辺の交差がないように、辺を水平線分や垂直線分 の列で描く 入力 出力 折れ曲り：0 直交描画 主な研究テーマの紹介 直交描画 辺の交差がないように、辺を水平線分や垂直線分 の列で描く 違う平面埋め込み 入力 出力 折れ曲り：0 直交描画 bend このグラフの違う平面埋め込みを考えましょう．この埋め込みでは，この緑の点がこの赤い閉路の内部に描かれています．埋め込みは違いますが，同じ配線です．この埋め込みから，得られた描画は折れ曲がりの個数が０で，最小です． 平面グラフ

直交描画 問題 bend 辺の交差がないように、辺を水平線分や垂直線分 の列で描く 入力 出力 折れ曲り：最小 直交描画 平面グラフ 主な研究テーマの紹介 直交描画 辺の交差がないように、辺を水平線分や垂直線分 の列で描く 問題 入力 出力 折れ曲り：最小 直交描画 bend 直交描画問題は，すべての平面埋め込みの中で，折れ曲がりの個数が最小の直交描画を見つける問題です． 平面グラフ

例 直交描画 描画 折れ曲り数： ４ bend bend 主な研究テーマの紹介 例えば，このグラフを次のように直交描画で描いてみましょう．得られた描画は４つの折れ曲がりを持ちます．

例 直交描画 描画 折れ曲り数：最小? No 折れ曲り数： ４ bend 主な研究テーマの紹介 最小折れ曲がりの個数は４でしょうか？違います．

例 直交描画 描画 埋め込み 折れ曲り数： ４ 反転 bend 主な研究テーマの紹介 もっと少ない数の折れ曲がりをもつ描画があります．このグラフの違う埋め込みを考えましょう．このように， 反転

例 直交描画 描画 埋め込み 反転 折れ曲り数： ４ bend 主な研究テーマの紹介 この埋め込みからこのように描画すれば，得られた描画に折れ曲がりが，まったくありません． 反転

例 主な研究テーマの紹介 折れ曲り数： ４ 直交描画 描画 bend 埋め込み 反転

例 主な研究テーマの紹介 折れ曲り数： ４ 直交描画 描画 bend 埋め込み 反転

例 主な研究テーマの紹介 直交描画 描画 bend 折れ曲り数： ４ 埋め込み

例 直交描画 描画 埋め込み 描画 最適 折れ曲り数： ４ 折れ曲り数： 0 bend 主な研究テーマの紹介 部分グラフを何回か反転させると，グラフとしては同じですが，違う平面埋め込みが得られます．この埋め込みからこのように描画すれば，得られた描画に折れ曲がりが，まったくありません． 描画 折れ曲り数： 0 最適

？ 既知の結果 研究成果：直並列グラフに対し （直交描画問題） 直並列グラフに対して O(n4) time 主な研究テーマの紹介 既知の結果 （直交描画問題） Δ≦4のとき, O(n4) time Δ≦3のとき, O(n3) time D. Battista, et al. 1998 直並列グラフに対して Δ≦3のとき, O(n) 時間 研究成果：直並列グラフに対し ？ 　いままで，直並列グラフに対し，最大次数Deltaが4以下のときに，Ｏ（ｎ４）の時間で折れ曲がりの個数が最小の描画を求まることが知られていました．最大次数Deltaが３以下のときには，少しだけ速くなり，Ｏ（ｎ３）になります．しかし，線形時間アルゴリズムが知られていませんでした．本研究では，最大次数が3以下のとき，折れ曲がりの個数が最小の描画を求める線形時間アルゴリズムの開発に成功しました．

アルゴリズム(G) 入力グラフG ： 最大次数 Δ≦3の直並列グラフ. If ∃ 菱形 Thenアルゴリズム( ), 描画 最適 見つける 主な研究テーマの紹介 アルゴリズム(G) 入力グラフG ：　最大次数 Δ≦3の直並列グラフ. If ∃ 菱形 Thenアルゴリズム( ), 最適 見つける 例 このアルゴリズムの概要は次のようになります．入力グラフＧは最大次数Deltaが3以下の直並列グラフです．ダイアモンドの形をした部分構造を持つときは，ダイアモンドをこのように１点に縮約して，得られたグラフの最適解，即ち折れ曲がり最小の直交描画を再帰的に求めます．その後で，縮約された点をこのようにダイアモンドに戻します．得られた描画は，明らかに，最小の折れ曲がり数を持ちます．例えば，このグラフにはダイアモンドが存在するので，それを1点に縮約し，また，ダイヤモンドがあるので，縮約し，まだダイアモンドがあるので，縮約する．これを繰り返すと，１点のグラフになります．その後，繰り返しダイアモンドを戻すことによって，折れ曲がりが最小の描画を得ることができます．いつもダイアモンドがあるわけではありません． 描画

アルゴリズム(G) 入力グラフG ： 最大次数 Δ≦3の直並列グラフ. If ∃ 菱形 Thenアルゴリズム( ), 主な研究テーマの紹介 アルゴリズム(G) 入力グラフG ：　最大次数 Δ≦3の直並列グラフ. If ∃ 菱形 Thenアルゴリズム( ), 最適 見つける Else If∃ 互い隣接している次数２の２点u,v 　 　Then u v u v ダイアモンドが存在しないときは，次の2つの構造のいずれかを持ちます．一つ目は互いに隣接している次数２の２点が存在します．そのとき，この辺を除去して，残ったグラフには必ず，折れ曲がりが最小の描画で，これら２つの点が外側にあるＵ形の描画があり，線形時間で見つけることができます．さきに，削除した辺を戻すことによって，全体の最適な描画が求まります．もし，互い隣接している次数２の２点が存在しないときは，必ず3角形が存在します．先と同様にその3角形を除去すると，残ったグラフには必ず折れ曲がりが最小のＵ形の直交描画があり，線形時間で求まります．3角形を折れ曲がり1個で描くことによって，全体の最適な描画が得られます．このようにして， Else∃ 三角形 K3. 最適

研究成果 （直交描画問題） 直並列グラフに対し Δ≦3のとき, O(n) 時間 直交描画 直並列グラフ 主な研究テーマの紹介 最大次数３以下の直並列グラフに対しは，線形時間で折れ曲がりが最小の直交描画を見つけることができます． 直交描画 直並列グラフ

グラフ描画 主な研究テーマの紹介 応用グラフ理論 計算理論 アルゴリズム グラフ分割 グラフ描画 グラフ彩色 グラフ 辺彩色 3つ目のテーマであるグラフ彩色について話します．

地図の彩色 主な研究テーマの紹介 点彩色 4色 4色 最初にグラフの点彩色を説明しましたが，これから，辺彩色について説明いたします．

辺彩色 時間帯： 転送時間：５ ５色 もっと速い転送方法？ 辺彩色 ファイル転送問題 1時間目 2時間目 3時間目 4時間目 5時間目 主な研究テーマの紹介 辺彩色 時間帯： 1時間目 2時間目 3時間目 4時間目 5時間目 転送時間：５ ５色 file 1 もっと速い転送方法？ file 2 file 7 file 6 file 3 file 4 ファイル転送問題を考えましょう．５つの計算機があって，その間でファイルを転送したいとします．例えば，この計算機とこの計算機の間にファイル１を転送したいとし，この計算機とこの計算機の間でファイル２を転送したいとし，以下同様とします．どのファイルもサイズが同じで，転送は1単位時間でできるとします．また，各計算機は通信ポートを１個しか持たないので，どの計算機も同じ時間帯に１つしか通信できません．この制約の下で，一番早くファイル転送を終了させる方法を求めたいわけです．例えば，１時間目に，ファイル１と３を転送し，２時間目にファイル２を，3時間目にファイル６とファイル７を，4時間目にファイル４を，5時間目にファイル５を転送します．かかる時間が5単位時間です．もっと速い転送方法が存在するでしょうか？ file 5 辺彩色 ファイル転送問題

辺彩色 時間帯： 転送時間：４ ４色 辺彩色 ファイル転送問題 色数 ファイル転送時間 1時間目 2時間目 3時間目 4時間目 5時間目 主な研究テーマの紹介 辺彩色 時間帯： 1時間目 2時間目 3時間目 4時間目 5時間目 転送時間：４ ４色 file 1 file 2 file 7 file 6 file 3 file 4 次のように4時間で転送することができます．各転送時間帯を色で表すと，左のようにグラフの辺彩色になっています．隣接している辺の色が異なっています．色数はファイル転送時間に対応しています．このように，ファイル転送スケジューリング問題は最小色数の辺彩色を見つけ問題として定式化できます． file 5 辺彩色 ファイル転送問題 色数 ファイル転送時間

点彩色問題 分割 ∈ NP困難 辺彩色問題 入力：グラフG 出力：最小色数で Gの点彩色 ｋ端子グラフ 主な研究テーマの紹介 点彩色問題 分割 ｋ個の端子 動的計画法 ＤＰ表のサイズ： 入力サイズの指数関数 辺型の問題について ｋ端子グラフ 1 2 k ２色数ｘｋ ∈ NP困難 最大次数が定数のとき 容易 入力：グラフG 出力：最小色数で　Gの点彩色 ＤＰ表のサイズ： 入力サイズの多項式 　　　木に対して、　　 　　∃　線形時間アルゴリズム　 JACM’82の結果 直並列グラフに対して、 点型の問題：　　∃　多項式時間アルゴリズム　 ＤＰ表（動的計画法） グラフ全体(任意のk) 部分k木（k=定数) 直並列グラフ（k=2) 辺型の問題：　　∃　多項式時間アルゴリズム　？　 木 (k=1) ｋ個の端子 動的計画法 点型の問題について ＤＰ表のサイズ： 入力サイズの多項式 容易 ｋ端子グラフ 1 2 k 色数ｋ 一般グラフに対し，点彩色問題がＮＰ困難ですが，直並列グラフに対し，動的計画法を用いて点彩色問題を解く線形時間アルゴリズムがすでに知られていました．ＤＰ表にこのように端子を同じ色で彩色しているときの最小色数と，このように端子を異なる色で彩色しているときの最小色数を覚え，それを並列接続や直列接続で更新します．同様な方法が部分ｋ木にも適用でき，線形時間で点彩色問題を解くことができます．つまり，部分ｋ木に対し，動的計画法を用いると，点彩色のように，点型の問題を線形時間で解くことが容易にわかります．その理由は，ｋ個の端子を持つ部分ｋ木の点型の問題については，ＤＰ表のサイズが色数のｋ乗で抑えることができ，入力サイズの多項式サイズになります．ここで，ｋは定数であるとしてます．しかし，辺彩色のような辺型の問題に対し，そう簡単にはいきません． 単純に考えると，DP表のサイズが２の色数かけるｋ乗になってしまいますので，入力サイズの指数関数になってしまいます．しかし，最大次数が定数のときに，ＤＰ表のサイズを入力サイズの多項式で抑えることができます． 辺彩色問題

ＤＰ表のサイズ： 入力サイズの多項式 ＤＰ表（動的計画法）

ｋ端子グラフ ｋ端子グラフ 点型の問題について 動的計画法 ｋ個の端子 1 2 k 容易 ＤＰ表のサイズ： 入力サイズの多項式 色数ｋ 辺型の問題について ｋ端子グラフ 困難 1 2 k ２色数ｘｋ

ｋ端子グラフ 容易 ＤＰ表のサイズ： 入力サイズの多項式 辺型の問題について 動的計画法 ｋ個の端子 困難 ＤＰ表のサイズ：

Σ Σ Gi 分解 各部分グラフGi の最大次数 ≦３ｋ ２ｋ≦ 辺彩色 Giの最大次数 ＝Gの最大次数 ＝Giの最大次数 Giの彩色指数 主な研究テーマの紹介 各部分グラフGi の最大次数 ≦３ｋ ２ｋ≦ 辺彩色 Giの最大次数 Σ ＝Gの最大次数 ＝Giの最大次数 Giの彩色指数 Gi ＝Gの最大次数 ＝ 部分ｋ木Gの 彩色指数 Σ Giの彩色指数 最大次数が大きいとき 最初に紹介したグラフの最大次数和分解を利用して，部分ｋ木の辺彩色問題を線形時間で解くことに成功しました． 部分ｋ木G

辺彩色問題 分割 ∈ NP困難 研究成果 入力：グラフG 出力：最小色数でGの辺彩色 部分k木に対して、 線形時間アルゴリズム 主な研究テーマの紹介 辺彩色問題 分割 ∈ NP困難 入力：グラフG 出力：最小色数でGの辺彩色 部分k木に対して、　　線形時間アルゴリズム 研究成果 グラフ全体(任意のk) 部分k木（k=定数) 直並列グラフ（k=2) 木 (k=1) 最後に今後の研究課題について話します．

発表の流れ 研究内容の概要 主な研究テーマの紹介 今後の研究課題 最後に今後の研究課題について話します．

今後の研究課題 グラフ描画 ∃ FPTAS ？ 近似困難？ 応用グラフ理論 計算理論 アルゴリズム グラフ分割 最大問題 最小問題 4 6 5 3 2 10 7 8 15 13 20 合計：19 4 6 5 3 2 10 7 8 15 13 20 合計：17 合計：7 合計： 5 合計：12 最大問題 ∃ FPTAS ？　 近似困難？ グラフ描画 応用グラフ理論 計算理論 アルゴリズム 最小問題 直並列グラフ 平面グラフ 木 グラフ分割について， 木の最大分割について近似アルゴリズムを与えましたが，直並列グラフや平面グラフや部分ｋ木に対し，ＦＰＴＡＳが存在するのか，あるいは近似困難なのかがまだ未解決です．また，最小分割問題，つまり，停電量を最小にする問題の近似アルゴリズムについて，木に対してすら未解決です． 部分ｋ木

今後の研究課題 ∃ 線形時間アルゴリズム？ グラフ分割 直交描画 最大次数が４以下の 直並列グラフ 最大次数：４ 直並列グラフ 二次元直交描画 直交描画について，最大次数が4以下の直並列グラフに対し，線形時間で折れ曲がりが最小の直交描画を見つけることができるかどうかがまだ未解決です．

今後の研究課題 グラフ分割 直交描画 三次元描画 ？ 二次元直交描画 折れ曲り：３ 最大次数：４ 直並列グラフ 三次元直交描画 折れ曲り：１ 三次元描画　？ 最大次数：４ 直並列グラフ 三次元直交描画 折れ曲り：１ また，このような3次元の描画もこれからの研究課題です．

今後の研究課題 グラフ分割 直交描画 グラフ彩色 今後の研究課題 ＷＤＭ光ネットワークの波長割り当てによく応用される道彩色も研究する予定です．例えば，リング上に配置したノードからこのような通信要求がきたとき，ポートaとeの間の通信，bとdの間の通信，bとfの間，cとeの間に，波長を割り当てる問題です．例えば，aとe間の通信とbとd間の通信は同じ辺を通っていますので，異なる波長を割り当てる必要があります．aとe間の通信とbとｄ間の通信は異なる辺だけを通っていますので，同じ波長を割り当ててもよいです．目標はできるだけ少ない波長を用いて，同時に多くの通信をすることです．この例では，赤色と緑色の２つの波長で十分です．このような問題は道彩色問題と呼ばれ，

今後の研究課題 ｛ ， ｝ a e b d f c d a f e c b グラフ分割 通信要求： 直交描画 グラフ彩色 道彩色という ｛　　　，　　｝ a e b d f c 直交描画 グラフ彩色 WDM光ネットワークの波長割り当て 道彩色という d a f e c b 異なる波長が必要 ＷＤＭ光ネットワークの波長割り当てによく応用される道彩色も研究する予定です．例えば，リング上に配置したノードからこのような通信要求がきたとき，ポートaとeの間の通信，bとdの間の通信，bとfの間，cとeの間に，波長を割り当てる問題です．例えば，aとe間の通信とbとd間の通信は同じ辺を通っていますので，異なる波長を割り当てる必要があります．aとe間の通信とbとｄ間の通信は異なる辺だけを通っていますので，同じ波長を割り当ててもよいです．目標はできるだけ少ない波長を用いて，同時に多くの通信をすることです．この例では，赤色と緑色の２つの波長で十分です．このような問題は道彩色問題と呼ばれ， 同じ波長でもよい 波長種類：２

今後の研究課題 グラフ分割 直交描画 グラフ彩色 ∃ よい近似アルゴリズム？ 道彩色という 今後の研究課題 ∃　よい近似アルゴリズム？ 道彩色という 一般のグラフに対し，ＮＰ困難であることが知られており，よい近似アルゴリズムはまだ知られていません．

今後の研究課題 グラフ分割 Graph Coloring Algorithms 直交描画 Part 1: Introduction Part 2: Vertex-Coloring Part 3: Edge-Coloring Part 4: Total Coloring Part 5: List Coloring Part 6: Cost Coloring 直交描画 グラフ彩色 道彩色 多重彩色 リスト彩色 彩色アルゴリズム に関する本の執筆

今後の研究課題 グラフ分割 Graph Coloring Algorithms 直交描画 Part 1: Introduction Part 2: Vertex-Coloring Part 3: Edge-Coloring Part 4: Total Coloring Part 5: List Coloring Part 6: Cost Coloring 直交描画 グラフ彩色 道彩色 多重彩色 リスト彩色 彩色アルゴリズム に関する本の執筆 ４色定理の証明を簡単化する そのほかに，多重彩色やリスト彩色も研究を続けます． また，いままで，長い間研究したグラフ彩色に関する成果をまとめ，彩色アルゴリズムに関する本を書いています．内容は6章から構成されています．彩色の紹介，点彩色，辺彩色，全彩色，リスト彩色，コスト彩色の章からなります． また，4色定理の証明を簡単化することなどもこれからの研究課題にしたいと考えています． K.Appel, W. Haken, 1976 N. Robertson, D.P. Sanders, P. Seymour, R. Thomas, 1997

今後の研究課題 グラフ分割 Graph Coloring Algorithms 直交描画 Part 1: Introduction Part 2: Vertex-Coloring Part 3: Edge-Coloring Part 4: Total Coloring Part 5: List Coloring Part 6: Cost Coloring 直交描画 グラフ彩色 道彩色 多重彩色 リスト彩色 彩色アルゴリズム に関する本の執筆 そのほかに，多重彩色やリスト彩色も研究を続けます． また，いままで，長い間研究したグラフ彩色に関する成果をまとめ，彩色アルゴリズムに関する本を書いています．内容は6章から構成されています．彩色の紹介，点彩色，辺彩色，全彩色，リスト彩色，コスト彩色の章からなります． また，4色定理の証明を簡単化することなどもこれからの研究課題にしたいと考えています．

今後の研究課題 Web情報検索アルゴリズム Web情報圧縮アルゴリズム Ｗｅｂ アルゴリズム グラフアルゴリズム 応用グラフ理論 計算理論 グラフ描画 まったく新しい分野として，Ｗｅｂアルゴリズムの研究を予定しています．Web情報検索アルゴリズムやＷｅｂ情報圧縮アルゴリズムです．

入力　：　キーワード（ユーザの欲しい情報） 検索エンジン 出力　：　Webページ 1）　Webから数十億のWebページを集める． 2）　各Webページを解析してリンクデータを作る． 3) リンクデータを元に出力するWebページを判断する． Web上の Webページとリンクの例

入力　：　キーワード（ユーザの欲しい情報） 検索エンジン 出力　：　Webページ 1）　Webから数十億のWebページを集める． 2）　各Webページを解析してリンクデータを作る． ①Webページにページ番号を振る． 1 ②リンクデータを作成． 2 この際，Webを Webページを点 リンクを有向辺 としたWebグラフで表す． 3 4 5 Web上の Webページとリンクの例

入力　：　キーワード（ユーザの欲しい情報） 検索エンジン 出力　：　Webページ 1）　Webから数十億のWebページを集める． 2）　各Webページを解析してリンクデータを作る． ①Webページにページ番号を振る． 1 ②リンクデータを作成． 2 この際，Webを Webページを点 リンクを有向辺 としたWebグラフで表す． 3 4 5 Webグラフの例 リンクは始点と終点の対で表される → (5, 4)

入力　：　キーワード（ユーザの欲しい情報） 検索エンジン 出力　：　Webページ 1）　Webから数十億のWebページを集める． 2）　各Webページを解析してリンクデータを作る． ①Webページにページ番号を振る． 1 ②リンクデータを作成． 2 始点番号 終点番号の集合 1, 4 3 4 5 Webグラフの例

入力　：　キーワード（ユーザの欲しい情報） 検索エンジン 出力　：　Webページ 1）　Webから数十億のWebページを集める． 2）　各Webページを解析してリンクデータを作る． ①Webページにページ番号を振る． 1 ②リンクデータを作成． 2 始点番号 終点番号の集合 1, 4 1 4 2 3, 4 ….. 3 4 5 Webグラフの例

入力　：　キーワード（ユーザの欲しい情報） 検索エンジン 出力　：　Webページ 1）　Webから数十億のWebページを集める． 2）　各Webページを解析してリンクデータを作る． ①Webページにページ番号を振る． ②リンクデータを作成． 検索エンジンでは このような リンクデータを使って 出力するページを 計算している 始点番号 終点番号の集合 1, 4 1 4 2 3, 4 …..

単純な方法では，整数1つごとに64bit必要． リンクデータの巨大さ リンクデータ 1 始点番号 終点番号の集合 1, 4 1 4 2 3, 4 ….. 2 , 9000000000 3 4 5 9,000,000,000 リンク1本あたりにかかる bit数を小さく（圧縮）したい 単純な方法では，整数1つごとに64bit必要． よって，リンク1本あたり64bit（8 byte）程度が必要になり， リンクデータ全体（約100億本の辺）には80GBが必要となる．

End

分散するコンピュータの余剰CPUパワーを活用して仮想的にスーパーコンピュータを実現するアルゴリズム 今後の研究課題 今後の研究課題 Ｗｅｂ アルゴリズム 分散するコンピュータの余剰CPUパワーを活用して仮想的にスーパーコンピュータを実現するアルゴリズム Web情報検索アルゴリズム Web情報圧縮アルゴリズム Web計算アルゴリズム

今後の研究課題 Web情報検索アルゴリズム Web情報圧縮アルゴリズム Web計算アルゴリズム Web可視化アルゴリズム Ｗｅｂ

今後の研究課題 Web情報検索アルゴリズム Web情報圧縮アルゴリズム Web可視化アルゴリズム Ｗｅｂ アルゴリズム 今後の研究課題 またグラフ描画を用いて，Ｗｅｂを可視化するアルゴリズムも研究予定です．

発表の流れ End 研究内容の概要 主な研究テーマの紹介 今後の研究課題 以上，いままでの研究内容および今後の課題について述べました．ご静聴ありがとうございます．また，何なりと，ご指摘，コメントなど，いただければ幸いです． End

End

今後の研究課題 Web情報検索アルゴリズム Web情報圧縮アルゴリズム Web計算アルゴリズム Web可視化アルゴリズム Ｗｅｂ

今後の研究課題 k：パラメータ f(k) ：k に関する関数 n：問題の入力サイズ f(k)  nO(1)時間アルゴリズム ここで、　 k：パラメータ f(k) ：k に関する関数 n：問題の入力サイズ 固定パラメータアルゴリズム f(k)  nO(1)時間アルゴリズム

地図の彩色 6色 5色?

地図の彩色 5色 4色?

地図の彩色 点彩色 4色 3色?

４彩色定理 課題 地図を4色で彩色可能 平面グラフを4色で点彩色可能 全ての次数が３の平面グラフを3色で辺彩色可能 提案：Francis Guthrie, 1852 最近の研究成果 証明：Appel と Haken,1976 4色 平面グラフを4色で点彩色可能 ある条件を満たす点ラベリングが存在する 証明：Tait, 1880 課題 全ての次数が３の平面グラフに対して、上記のラベリングが存在する 全ての次数が３の平面グラフを3色で辺彩色可能

(2)完全近似スキーム （FPTAS） 計算時間 各点 ･･････････････ O(F 2) グラフの点数： n 根 3 20 4 7 8 6 5 9 15 25 動的計画法

Pseudo-Polynomial-Time Algorithm Computation time for each vertex ･･････････････ O(F 2) There are n vertices. Computation time O(F 2n) The algorithm takes polynomial time if F is bounded by a polynomial in n.

(2) FPTAS Let all demands and supply be positive real numbers. For any e, 0< e <1, the algorithm finds a partition of a tree T such that OPT – APPRO < e OPT in time polynomial in both n and 1/e . n : # of vertices

(2) FPTAS The algorithm is similar to the previous algorithm. fulfillment marginal power t sampled fulfillment

(2) FPTAS total error < error/merge × # of merge < 2t × n The algorithm is similar to the previous algorithm. fulfillment marginal power OPT – APPRO < 2nt OPT t sampled fulfillment APPRO

(2) FPTAS md: max demand Error OPT – APPRO < 2nt 7 4 3 6 2 9 5 15 25 9 md = 9

(2) FPTAS md: max demand Error OPT – APPRO < 2nt md ≦ OPT ≦ e OPT OPT – APPRO < e OPT error ratio

(2) FPTAS md: max demand Error OPT – APPRO < e OPT Computation time marginal power t Sampled fulfillment

Conclusions General graphs (1) MAXSNP-hard (APX-hard) 4 6 5 3 2 10 7 8 12 15 13 25 No PTAS unless P=NP Trees NP-hard 7 4 3 6 2 9 5 15 25 (2) FPTAS

時間帯： 2色 [1,2] [0,2] [1,2] [0,2] [g,f]彩色 ファイル転送問題 1時間目 2時間目 3時間目 4時間目 5時間目 2色 [1,2] [0,2] [1,2] [0,2] file 1 file 2 file 7 file 6 file 3 file 4 file 5 [g,f]彩色 ファイル転送問題

[0,1]彩色 辺彩色 [0,1]

[g,f]彩色問題 分割 ∈ NP困難 研究成果 入力：グラフG 出力：最小色数でGの[g,f]彩色 部分k木に対して、　　線形時間アルゴリズム 研究成果

全彩色問題 分割 以下の条件を満たすように点と辺を彩色することである。 隣接点に異なる色 隣接辺に異なる色 隣接点と辺に異なる色

全彩色問題 分割 ∈ NP困難 入力：グラフG 出力：最小色数でGの全彩色 部分k木に対して、　　線形時間アルゴリズム 研究成果