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

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

(1) 線形時間アルゴリズム理論の確立
インターネットなどの接続構造を表すグラフには特徴があり,木構造を一般化した形をしている,即ち“木幅” が小さいグラフである。そのようなグラフに対してはほとんど全ての組み合せ問題が極めて高速に解ける,即ち入力されたグラフの大きさに比例した程度の時間で解けることを示した。この研究分野が発展する端緒になったのは貢献者らの論文“Linear-time computability of combinatorial problems on series-parallel graphs”であり,コンピュータサイエンスで最も権威ある雑誌JACMに掲載され,100編以上もの論文で引用されている。この論文は,直列接続と並列接続を繰り返して得られるグラフ上の多くの組み合せ問題に対する線形時間アルゴリズムの統一的設計理論を与えており,線形時間アルゴリズム理論の分野に与えたインパクトは極めて大きい。また,木幅の小さいグラフは“部分k木”と呼ばれるが,部分k木に対しても辺素な道や,辺彩色を求めるアルゴリズムを与えており,VLSIの配線やマルチプロセッサーのタスクスケジューリングに応用されている。

(2) 離散アルゴリズムの効率化
本研究のもう一つの大きな業績として,グラフ特に平面グラフに関する理論の展開とアルゴリズムの効率化が挙げられる。平面グラフの埋込み,彩色,ハミルトン閉路,独立点集合,多種フロー問題など重要な組み合せ問題のほとんど全てに対し,極めて効率のよいアルゴリズムを与えている。それらの多くは線形時間で終了するため最良である。これらの効率化にはまったく新しい着想による理論と設計法が導入されている。これら平面グラフの理論とアルゴリズムに関する成果は約100編もの論文として,SIAM J. ComputingやIEEE Trans. CADなどの国際学会誌,STOCやICALPなどの国際会議で発表されている。これらの成果をまとめたのが英文著書Planar Graphs: Theory and Algorithms (North-Holland社)である。N. Biggs教授やA.A. Bertossi教授は書評で本書を平面グラフの理論とアルゴリズムに関する専門書として高く評価している。

(3)グラフ描画という研究分野の開拓と育成
グラフをいろいろな条件の下で最適に描画することは,インターネットの接続構造を見やすく表示するためばかりでなく,科学技術の様々な領域で現れる重要な問題である。本研究では,世界で最初にグラフ描画についてアルゴリズムの立場から研究を開始し,平面グラフの全ての面を凸多角形で描画する凸描画が存在するかどうか判定し,存在する場合には凸描画を見つける線形時間アルゴリズムを1984年に与えた。また,連結度が高い平面グラフは,縦も横も点数の半分以下であるような小さい平面格子の格子上に点を配置して,各辺を直線で描けることを示し,永年の未解決問題を解決した。この他にも,箱矩形描画や内部矩形描画などの新しい描画法を提案し,そのアルゴリズムを与えるなど,グラフ描画の分野を開拓した。これらの成果をまとめたのが英文著書Planar Graph Drawing(World Scientific社)である。


さらに詳しく知りたい読者は「専門向け」のページもご覧ください。


関連する研究を検索

分野のカテゴリ

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

関連する出来事

データなし

世の中の出来事

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

Webページ

データなし

博物館等収蔵品

データなし

キーワード

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