文献

J-GLOBAL ID：202002239481218925   整理番号：20A0275964

経路ネットワーク上の最小和kシンク問題【JST・京大機械翻訳】

Minsum k-sink problem on path networks

著者 (5件)： Benkoczi Robert (Dept. of Math & Computer Science, Univ. of Lethbridge, Lethbridge, Canada) ,  Bhattacharya Binay (School of Computing Science, Simon Fraser University, Burnaby, Canada) ,  Higashikawa Yuya (School of Social Information Science, Univ. of Hyogo, Kobe, Japan) ,  Kameda Tsunehiko (School of Computing Science, Simon Fraser University, Burnaby, Canada) ,  Katoh Naoki (School of Social Information Science, Univ. of Hyogo, Kobe, Japan)
資料名： Theoretical Computer Science  (Theoretical Computer Science)
巻： 806  ページ： 388-401  発行年： 2020年 
JST資料番号： T0022A  ISSN： 0304-3975  CODEN： TCSDIQ  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： オランダ (NLD)  言語： 英語 (EN)

抄録/ポイント： 著者らは,すべての避難時間の合計を最小化する一般的な端部容量を有する経路ネットワーク上にkシンクの集合を位置決めする問題を考察した。著者らは,最初に,エッジ容量が不均一であるとき,nが頂点の数であるとき,O(knlog4n)時間アルゴリズムを提示した。次に,エッジ容量が一様であるとき,O(knlog3n)時間アルゴリズムを提示した。k=1とエッジ容量が不均一な特別な場合に対するO(nlog n)時間アルゴリズムも示した。Copyright 2020 Elsevier B.V., Amsterdam. All rights reserved. Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： *ネットワーク ,  アルゴリズム ,  避難
準シソーラス用語： 避難時間 , 【Automatic Indexing@JST】

著者キーワード (5件)： 施設配置 ,  シンク位置問題 ,  避難問題 ,  最小和基準 ,  ネットワークにおける動的フロー

分類 (2件)： 図形・画像処理一般  (JE04010I) ,  グラフ理論基礎  (IA02020S)

タイトルに関連する用語 (2件)： 経路 ,  シンク