1. HOME
  2. 電気・情報関連(専門)
  3. 研究情報(登録番号1915)

効率的離散アルゴリズム設計の先駆的研究

 インターネットやVLSIなど高度な情報科学技術の発展に伴い、膨大な点と辺の接続構造を表す巨大なグラフ上で様々な組合せ問題を効率良く解く離散アルゴリズムを開発することが望まれているが、多くの問題はいわゆるNP完全であり、一般のグラフに対しては組合せ爆発により効率良く解けそうにないことが分かっていた。
 本研究は、インターネットなどの接続構造やVLSIの配線を表すグラフなど、実用上よく現れるグラフは木構造を一般化した形をしている、すなわち“木幅”が小さいという特徴があることに注目し、そのようなグラフに対してはほとんどすべての組合せ問題が線形時間で解ける、すなわち入力されたグラフの点数に比例した時間で解けることを示した。特に直列接続と並列接続を繰り返して得られる“直列系グラフ”に対しては、線形時間アルゴリズムを自動的に設計する統一的論理を世界に先駆けて確立した。また、木幅が小さいグラフに対しては、点彩色や点素道探索などいわゆる点型の組合せ問題を解くアルゴリズムは容易に設計できるが、辺彩色など“辺型”の問題を解くアルゴリズムは設計できないであろうと予想されていた。しかし、本研究では、最大次数制限辺集合分解など全く新しい着想による理論を導入し、辺彩色や辺素道を求める効率の良いアルゴリズムの開発に成功した。
 本研究のもう一つの大きな業績として、平面グラフに関する理論の展開とアルゴリズムの効率化が挙げられる。平面グラフの埋込み、彩色、ハミルトン閉路、独立点集合、多種フロー問題など重要な組合せ問題のほとんどすべてに対し、極めて効率の良いアルゴリズムを与えている。それらの多くは線形時間で終了するための最良である。これらの効率化には全く新しい着想による理論と設計法が導入されている。これらの成果をまとめたのが英文集「Planar Graphs : Theory and Algorithms」(North-Holland社)であり、平面グラフの理論とアルゴリズムに関する専門書として数多くの書評で高く評価されている。
 更に本研究では、世界で最初にグラフ描画についてアルゴリズムの立場から研究を開始し、平面グラフのすべての面を凸多角形で描画する凸描画が存在するかどうか判定し、存在する場合には凸描画を見つける線形時間アルゴリズムを与えた。また、連結度が高い平面グラフは、縦も横も点数の半分以下であるような小さい平面格子に点を配置して、各辺を直線で描けることを示し、永年の未解決問題を解決した。このほかにも、箱方形描画や内部方形描画や折れ曲がり最小直交描画などの新しい描画法を提案し、それらのアルゴリズムを与えるなど、グラフ描画の分野を開拓した。


 本研究の成果に対して、電子情報通信学会は、2008年、西関隆夫、周暁に業績賞を贈った。

関連する研究を検索

分野のカテゴリ

通信
(電子情報通信の基礎・境界技術)

関連する出来事

データなし

世の中の出来事

2008
後期高齢者医療制度がスタートする。
2008
米投資銀行リーマン=ブラザースが経営破綻する(リーマン=ショック)。

Webページ

データなし

博物館等収蔵品

データなし

キーワード

離散アルゴリズム、平面グラフ、グラフ描画
Page Top