研究内容

 離散数学(グラフ理論、組合せ論など)の観点から、組合せアルゴリズムの研究をしています。特に「21世紀に向けての超大規模集積回路自動設計研究体(CAD21)」に参加していたこともあり、VLSIレイアウト自動設計における配置・配線を動機とする組合せ問題を中心に研究してきました。

 現在の主要なテーマは以下の2つです。

  • 組合せ構造の表現法
  • グラフの描画

 また、現在のテーマに至る道(若干専門家向け)と研究成果の情報(専門家向け)を公開していますので興味のある方はどうぞ。

組合せ構造の表現法

 離散構造あるいは組合せ構造の表現法を考えています。適切な表現法は(i) 数え上げの問題、(ii) 組合せ最適化問題に大きく貢献します。

 (i) 離散構造の数え上げ、すなわち対象とする離散構造の総数を与えることは組合せ論のテーマの1つでもあります。例えばグラフ理論における古典的な定理があります。

「n点のラベル付き木の総数はnn-2である(Caylay,1889)」

 Caylayの定理はn点のラベル付き木の集合からn以下の自然数をn-2個並べてできる列の集合への一対一対応(全単射)を構成するすることで証明されます。つまりラベル付き木という離散構造は長さn-2の数の列によって表現されることになります。

 ある離散構造を数え上げる場合、それを他のより扱いやすい(数えやすい)表現に変換するという手法が有効であることを示す1つの例でしょう。

 (ii) 組合せ最適化問題はある離散構造の中で特定の条件を満たすものを探索する問題ですが、多くは探索空間(対象となる離散構造の集合)が非常に大きく、また効率的なアルゴリズムが望めない(NP困難である)ものがほとんどです。そのため、一般には発見的探索(メタ戦略)が用いられることになります。アルゴリズムの性能は探索すべき空間(解空間)は対象が計算機の中でどう表現されているかによって大きく左右されます。ここでも離散構造を扱いやすい表現に変換することが鍵となってきます。

グラフの描画

 グラフを平面あるいは空間に描く方法を考えています。特に格子描画、直交線分描画に関心があります。

 抽象的にはグラフは点集合Vとその2要素の対(枝あるいは辺と呼ぶ)からなる集合Eによって定義されます。グラフの描画は点集合Vの要素を実際に空間の点で表し、Eの要素を対応する点を結ぶ曲線で表してできる図形です。

 描画は単にグラフを人間が認識するための表現にとどまらず、VLSIのマスクパターンやプリント基板の設計などにも登場します。

 グラフの描画はそれが登場する場面に応じて、いろいろな制約が課されることがあります。そのためいろいろな描画の形式が提案され、研究されてきました。以下にいくつか紹介しましょう

枝の形状に対する制約
折れ線による描画
(Polyline drawing)

各枝が折れ線によって構成されている描画

直線分描画
(Straight-Line Drawing)

各枝が全て直線分である描画

直交線分描画
(Orthogonal Drawing)

各枝が水平・垂直の2種類の直線分によって構成される描画

点の位置に対する制約
格子描画
(Grid Drawing)

各点のxy座標が全て整数である描画

トポロジー的な制約
平面描画
(Planar Drawing)

どの2枝も交差しない描画

ページのトップへ戻る