2024-03-29T00:18:23Z
https://niigata-u.repo.nii.ac.jp/oai
oai:niigata-u.repo.nii.ac.jp:00003313
2022-12-15T03:36:26Z
423:424:425
453:454
ネットワーク上の最適点数充足勢力圏図
ネットワーク上の最適点数充足勢力圏図
An Optimal Cardinality-Constrained Territory Map on a Network
森泉, 隆
築山, 修治
篠田, 庄司
仙石, 正和
白川, 功
copyright(C)1988 IEICE
点集合V,各枝の枝長が指定されている枝集合E,および母点と呼ばれるk個の点をもつネットワークNが与えられたとき,Vを被覆する点の集合の族M={T_i}の各T_iが,互いに素で,母点c_iを含むが他の母点を含まずL_i≦|T_i|≦N_iを満たすならば,T_iをc_iの勢力圏といい,MをNの点数充足勢力圏図という.ここで,|T_i|はT_iの要素数を表し,L_iおよびN_iは各母点c_iに対して指定された1対の正定数である.c_iの勢力圏T_iに対して,f(T_i)をc_iからT_iの各点への最短路長の総和とし,点数充足勢力圏図M={T_i}に対して,F(M)をf(T_i)の総和としたとき,任意の点数充足勢力圏図M ′に対して,F(M)≦F(M ′)を満たすMを最適点数充足勢力圏図という.本論文では,最適点数充足勢力圏図を見出す問題について考察し,時間およびスペース複雑度がそれぞれO(|V|(|E|+k log k))およびO(|V|+|E|)のアルゴリズムを提案する.ネットワーク上の最適点数充足勢力圏図は,要素関係を考慮した割当て問題との関連で基本的役割を果たす.
電子情報通信学会
1988-10
jpn
journal article
http://hdl.handle.net/10191/22423
https://niigata-u.repo.nii.ac.jp/records/3313
http://www.ieice.org/jpn/trans_online/
AN10013345
09135707
電子情報通信学会論文誌. A, 基礎・境界
電子情報通信学会論文誌. A, 基礎・境界
J71-A
10
1917
1929
https://niigata-u.repo.nii.ac.jp/record/3313/files/J71-A_10-_1917-1929.pdf
application/pdf
1.2 MB
2019-07-30