容量空間における最適勢力圏図

概要

論文の詳細を見る
Vを点といわれる要素からなる空でない集合とし、容量関数といわれるV×VからR^-_+への関数γが定義されているとき、(V;γ)を容量空間という。また、母点集合といわれるVの部分集合C（要素を母点という）が指定されているものとする。和集合がVとなるVの部分集合族M={T(c)|c∈C}の各部分集合T(c)が互いに素で、母点ｃを含むが他の母点を含まなければT(c)をcの勢力圏といい、Mを(V;γ)の勢力圏図という。各母点cの勢力圏T(c)に対してf(T（ｃ）)をcとT(c)の各点vとの容量(γ(c,v))の総和とする。勢力圏図Mに対してF(M)をf(T(c))の総和としたとき、最大のF(M)をとる勢力圏図を最適勢力圏図という。本論文では、容量空間における最適勢力圏図の構成と母点集合の変化に伴う最適勢力圏図の修正について考察し、2点間の最大流量を容量関数とする無向ネットワークNにおいてはO(knm log n)の手間で最適勢力圏図を構成できることを示す。但し、k,n,mはそれぞれCの要素数、Nの点数、Nの枝数を表す。また非母点の母点への変更やその逆の場合の最適勢力圏図の修正がO(log|V|)で可能となるネットワークを容量空間から構成する。
電子情報通信学会の論文