東北大学大学院情報科学研究科 -- Graduate School of Information Sciences,Tohoku University --

西関隆夫教授が平成20年度科学技術分野の文部科学大臣表彰科学技術賞（研究部門）を受賞

『離散アルゴリズム設計法と秘密情報共有法に関する研究』

■業績概要　インターネット，交通網，VLSI配線などに関する多くの問題は，点およびそれらを結ぶ辺からなる"グラフ"上の離散問題として定式化されるため，グラフ問題を高速に解くアルゴリズムの開発研究が望まれていた。また，秘密情報をいくつかの分散情報に分割し，それらから元の秘密情報を復元させる一般的な"秘密分散共有法"の開発が急務であった。　本研究では，構造的グラフや平面グラフのほとんど全ての組合せ問題に対し，高速アルゴリズムを自動的に設計する方法論を確立するとともに，秘密共有する各構成員に分散情報を複数個割り当てる複数割り当て法を発明し，いかなるアクセス構造も実現できることを示した。　本研究により，構造的グラフや平面グラフに対し極めて効率的なアルゴリズムが自動的に設計でき，任意のアクセス構造を有する秘密分散共有法が実現できるようになった。　本成果は，インターネットのルーティングやVLSI配置・配線，USBメモリの管理技術や秘密鍵共有技術に寄与することが期待される。
		西関　隆夫　教授

賞状

■主要論文「Linear-time computability of combinatorial problems on series-parallel graphs」 J. Association for Computing Machinery, Vol. 29, No.3, pp.623-641, 1982年7月発表「Multiple assignment scheme for sharing secret」J. Cryptology, Vol.6, pp.15-20, 1993年発表 ■主要著書「Planar Graphs : Theory and Algorithms」North-Holland, 1988年発表「Planar Graph Drawing」World Scientific, 2004年発表

西関 隆夫 教授が平成20年度科学技術分野の文部科学大臣表彰科学技術賞（研究部門）を受賞

西関隆夫教授が平成20年度
科学技術分野の文部科学大臣表彰科学技術賞（研究部門）を受賞