文献

J-GLOBAL ID：201702269788038951   整理番号：17A1256197

制限された最小単一源最短経路ツリー展開問題【Powered by NICT】

The restricted minimum single source shortest path tree expansion problem

著者 (4件)： Wang Haiyan (School of Statistics and Mathematics, Yunnan University of Finance and Economics, Kunming, China) ,  Deng Weiqi (School of Statistics and Mathematics, Yunnan University of Finance and Economics, Kunming, China) ,  Huang Binchao (China Mobile Group Yunnan Co., Ltd., Kunming, China) ,  Li Jianping (Department of Mathematics, Yunnan University, Kunming, China)
資料名： IEEE Conference Proceedings  (IEEE Conference Proceedings)
巻： 2017  号： ICIS  ページ： 63-68  発行年： 2017年 
JST資料番号： W2441A  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： アメリカ合衆国 (USA)  言語： 英語 (EN)

抄録/ポイント： 三種類の最小単一ソース最短経路ツリー展開問題を考察した。n頂点,m辺と正定値H,w(e)とG(V, E; w, c, b; s)は辺の長さが無向連結グラフが与えられたとき,C(e)は,エッジeの容量は,(e)は,エッジeの容量を増加させる単価,Hは,与えられた容量制限値であるとは,Gの固定頂点である全てのエッジe=uvεEでは,容量C(UV)は<Hならば,エッジuvの容量を増加させると,増加する値はadd(紫外)=H C(UV)である容量C(UV)は,≧Hならば,エッジuvの容量を増加させる必要なく,増加値はadd(紫外)=0であった。Gのスパンニング木Tを発見,vεV毎,d_T(s,v)d_T(s,v)≦αdG(s,v)+β(α, β≧0)はTにおけるs Tからの距離であることをこのような,d_G(s,v)とは,G中のS Tからの距離は,αとβは定数である。目的は,T,すなわち分Σ_e∈E(T)付加(e)B(e)中のすべてのエッジの全拡大コストを最小化することである。WEは,制限された最小単一ソース最短経路ツリー展開問題と呼ぶ。問題であるNP ハード,のための発見的アルゴリズムを設計した。各頂点vεVの拘束条件d_T(s,v)≦αd_G(s,v)+β(α, β≧0)におけるα1,β0,新しい問題と呼ぶ拡張制限最小単一ソース最短経路ツリー展開問題とそのための強く多項式時間アルゴリズムを設計した。拡張制限最小単一ソース最短経路ツリー展開問題に基づいて,著者らは種々の目的でより広範な問題を研究した:単一源最短経路木T(根としてVεVを使うことができる)を見出し,T中のすべてのエッジの全拡張コストが最小になるような,すなわち分Σ_e∈E(T)は追加(e)。b(e)。一般制限最小単一ソース最短経路ツリー展開問題と呼ぶ,のための多項式時間アルゴリズムを設計した。Copyright 2017 The Institute of Electrical and Electronics Engineers, Inc. All Rights reserved. Translated from English into Japanese by JST【Powered by NICT】

シソーラス用語： *スパンニング木 ,  束縛条件
準シソーラス用語： 多項式時間アルゴリズム ,  発見的アルゴリズム ,  連結グラフ ,  *最短経路 , 【Automatic Indexing@JST】

分類 (1件)： グラフ理論基礎  (IA02020S)

タイトルに関連する用語 (3件)： 制限 ,  最短経路 ,  展開