グラフネットワークにおけるフローの概念は、輸送や通信の効率化だけでなく、データのクラスタリング、ネットワークの信頼性解析など、幅広い応用を持っている。その理由は、最大流最小カット定理によって、最大流問題と最小カット問題が表裏一体の関係にあることが広く知られ、そのためにフローを用いたモデル化が豊かな表現力を有することにある。実際、最大流問題の応用として知られている事例の多くは、フローそのものよりもカットを求めている。にもかかわらず、最小カットを計算するには、最大流アルゴリズムを経由するのが定石であった。
本研究では、1990年に発見された連結度の階層性を形成するグラフの森分解に基づき最小カット（枝連結度）を計算するアルゴリズムを構築した。このアルゴリズムは、グラフの頂点を最大隣接順序で順序付けすれば、最後の2頂点間の連結度が線形時間で検出できるという新しい動作原理に基づいているのが大きな特徴である。最大流を経由せずに最小カットを計算するという点で従来の手法とは全く異なった新たなアルゴリズムの出現は驚きをもって迎えられ、理論的なブレークスルーとなった。実用的にも、プログラムとしての実装が容易であり、極めて高速であることが報告されている。これらの特徴から、このアルゴリズムはCook, Cunningham, Pulleyblank, Schrijver (1998), Korte, Vygen (2000) など、離散最適化分野の代表的な教科書において、標準的解法として紹介され、世界中の大学・大学院で教えられている。
更に、本研究では、最大隣接順序に基づく最小カットアルゴリズムを発展させる形で、準最小カットの列挙、カクタス構造構成問題、極値頂点集合族問題、枝連結度増大問題、供給点配置問題などのより複雑な連結度問題を解く高速かつエレガントなアルゴリズムが体系的に開発された。特に、森分解に基づいた疎化法と呼ばれる方法は、アルゴリズムの標準的な設計手法の一つとして定着している。
本研究によるグラフ連結度アルゴリズムと正モジュラー集合関数の理論は、オリジナリティの高い手法の開発と新しい理論体系の確立により、電子工学と情報通信に応用を持つ先駆的基礎的研究として重要な貢献を果たした。これは、計算理論、離散数学、オペレーションズリサーチ分野の最適化の研究者の注目の的となり、それらの研究分野の協調と融合の大きな推進力となった。


　本研究の成果に対して、電子情報通信学会は、2010年、茨木俊秀、永持仁に業績賞を贈った。

文献

[1] H. Nagamochi and T. Ibaraki,　"A linear-time algorithm for finding a sparse　k-connected spanning subgraph of a k-connected graph, Algorithmica," Vol. 7, pp. 583-596, 1992.

[2] H. Nagamochi and T. Ibaraki, "Computing the edge-connectivity of multigraphs and capacitated graphs," SIAM J. Discrete Mathematics, Vol. 5, No.1, pp. 54-66, 1992.

[3] H. Nagamochi and T. Ibaraki, Algorithmic Aspects of Graph Connectivities, Encyclopedia of Mathematics and Its Applications, Cambridge University Press, 2008.