無向ネットワークにおける流量要求を満たす施設配置問題

• Item type: SIG Technical Reports(1)
• 公開日: 2000-05-19
• タイトル: 無向ネットワークにおける流量要求を満たす施設配置問題
• タイトル / 言語: en
• タイトル: Locating Sources to Meet Flow Demands in Undirected Networks
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 大阪大学大学院基礎工学研究科システム人間系専攻システム科学分野
• 著者所属: 東京大学大学院工学系研究科計数工学専攻
• 著者所属: 大阪大学大学院基礎工学研究科システム人間系専攻システム科学分野
• 著者所属: 大阪大学大学院基礎工学研究科システム人間系専攻システム科学分野
• 著者所属(英): en
• 著者所属(英): Division of Systems Science, Graduate School of Engineering Science, Osaka University
• 著者所属(英): en
• 著者所属(英): Department of Mathematical Engineering and Information Physics, Graduate School of Engineering, University of Tokyo
• 著者所属(英): en
• 著者所属(英): Division of Systems Science, Graduate School of Engineering Science, Osaka University
• 著者所属(英): en
• 著者所属(英): Division of Systems Science, Graduate School of Engineering Science, Osaka University
• 著者名: 新, 浩治; 岩田, 覚; 牧野, 和久; 藤重, 悟
• 著者名(英): Kouji, Arata; Satoru, Iwata; Kazuhisa, Makino; Satoru, Fujishige
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: この論文では，無向ネットワークにおいて，各点υに対してd(υ)の流量を送ることが可能な，最小費用の点集合Sを発見する問題を扱う．この問題は一般的にはNP?困難であるが，田村らは，各点の費用が一定である特殊な場合の問題を解く食欲解法を提案している．我々は線形計画双対性を用いて，この貪欲アルゴリズムにおける正当性のより単純な証明を与え，計算時間をO(n^2M)からO(nM)へと改良する．ここでnはネットワークの点の数であり，Mはnの点とmの枝を持つネットワークにおける最大フローの計算時間を定義する．我々はまた，一定の要求容量と任意の費用を持つ特殊な場合の問題を解くO(n(m+nlogn))のアルゴリズムを提案する．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: This paper deals with the problem of finding a minimum-cost vertex subset S in an undirected network such that for each vertex ν we can send d(ν) units of flow from S to ν. Although this problem is NP-hard in general, Tamura et al. have presented a greedy algorithm for solving the special case with uniform costs on the vertices. We give a simpler proof on the validity of the greedy algorithm using linear programming duality and improve the running time bound from O(n^2M) to O(nM), where n is the number of vertices in the network and M denotes the time for max-flow computation in the network with n vertices and m edges. We also present an O(n(m+nlogn)) time algorithm for the special case with uniform demands and arbitrary costs.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 情報処理学会研究報告アルゴリズム（AL）; 巻 2000, 号 41(2000-AL-073), p. 19-25, 発行日 2000-05-19
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会