ネットワーク構造を有する問題に対するアルゴリズムの開発

点击翻译按钮获取中文摘要

重み付きグラフの最小重みのカットはグラフ・ネットワーク理論における基本的な概念であり、フローの概念と合わせて豊かな離散数学的な構造を作っている。この構造を利用して、多くの組み合わせ最適化は、フローやカットの概念に基づいた部分問題に帰着して解かれている。従って、最小重みのカットあるいはそれに準じる十分小さいカットに関する情報を効率良く計算するアルゴリズムを設計することは、様々な組み合わせ最適化問題を解く算法を設計する上で大変重要である。本研究では、当研究者らが最近開発した最小重みのカットを高速に検出するアルゴリズムを実際にプログラムし、実際にその計算速度の速さを確認した(H.Nagamochi,T.Ono and T.Ibaraki,Implementing an efficient minimum capacity cut algorithm,Math.Prog.,67,1994,325-341)。この他、1つの重み付きグラフの持つすべての最小重みのカットを簡潔に表現するデータ構造に関する表現の一意性(H.Nagamochi and T.Kameda,Canonical cactus representation for minimum cuts,J.of Japan SIAM,11 1994,343-361)やその表現を高速に構築するアルゴリズムの設計を行った(H.Nagamochi and T.Kameda,Constructing cactus representation for all minimum cuts in an undirected network,(to appear in ORSJ))。さらに、最小重みに準じる十分小さいカットに関して、その個数に関する理論的上界・下界を数学的に導出する(H.Harada,Z.Sun and H.Nagamochi,An exact lower bound on the number of cut-sets in multigraphs,Networks 24,1994,429-443)とともに、そのようなカットを列挙する効率の良いアルゴリズムを開発した(H.Nagamochi,K.Nishimura and T.Ibaraki,Computing all small cuts in undirected networks,Lectures Notes in Computer Science 834,Springer-Verlag,.1994,190-198)。このとき得られた手法を応用し、グラフの連結度を最小費用(=最小本数の枝)をにより増加させる問題を解く計算の手間を軽減させた(H.Nagamochi and T.Ibaraki,A faster edge splitting algorithm in multigraphs and its application to the edge-connectivity augmentation problem(to appear in IPCO95,Copenhagen))。以上の成果は、組み合わせ的手法を用いて、通信網,電力網、VLSIの配線問題などの解析・設計を行う上で有用であると考えられる。