歴代受賞者一覧

受賞者紹介

永持　仁（ながもち・ひろし）
昭和35年1月1日生まれ
豊橋技術科学大学情報工学系　教授

贈賞の理由

グラフアルゴリズムに関する研究

インターネットに代表される情報ネットワークでは、個々のノードがリ ンクによって直接あるいは間接に接続されている。ネットワークの性質の解析や、要求を満たすネットワークの設計を計算機の支援のもとに高速に行うことは、情報基盤技術や社会経済活動に重要な役割を果たすために、重点的に研究が行われてきた。

二つのノード間で相互通信できる情報量を求めるために、従来は、ネ ットワークフローに基づく反復アルゴリズムが使われていた。永持教授はこの問題に対して、ネットワークフローを用いない、最小カットのアルゴリズムを考案した。最大隣接順序というノードの順序づけを発見し、これがほぼ線形時間で求まることを示し、この順序づけを利用することによって、高速に問題を解くアルゴリズムを考案した。その発表以来、ネットワークアルゴリズムの国際的な研究は、ネットワークフローによらず、永持教授のアルゴリズムに基づく方向に進展している。永持教授は、カットの研究をさらに進め、ネットワークの高信頼性問題、すなわち、既存のネットワークの信頼度を増し混雑度を軽減するために新しくリンクを張る場合、回線の敷設費用を考慮した最適なネットワークを設計する問題に適用し、この問題に対する解を高速に求めるアルゴリズムを開発した。

ネットワークの性質を解析するためには、多くの場合反復による計算を必要とする。従来は、反復のたびにネットワークのすべてのリンクを調べる手法が用いられていた。永持教授は、特別に前処理して選んだリンクのみを繰り返し調べ、必要に応じてリンクを付け加えることで、ネ ットワークの性質が解析可能であることを実証し、この成果をもとにスパース化とよばれる技法を開発した。

永持教授の与えた解法は、深い数理的な理論に基づくもので、その理論の適用範囲は、ネットワークの問題にのみ限定されるものではなく、集合関数理論の分野などへも応用されている。このように、永持教授の業績は、独創性に富み新分野を切り拓くとともに応用範囲も広く数理論的にも華麗であり、いずれも反響は極めて大きく、本賞を贈るにふさわしいものである。

上に戻る

※所属名および役職は、受賞時のものです。