木構造の動的ネットワークにおける施設配置問題

• Item type: SIG Technical Reports(1)
• 公開日: 2001-11-27
• タイトル: 木構造の動的ネットワークにおける施設配置問題
• タイトル / 言語: en
• タイトル: Optimal Sink Location Problem for Dynamic Flows in a Tree Network
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 大阪大学大学院基礎工学研究科システム科学分野
• 著者所属: 大阪大学大学院基礎工学研究科システム科学分野
• 著者所属: 大阪大学大学院基礎工学研究科システム科学分野
• 著者所属(英): en
• 著者所属(英): Division of Systems Science, Graduate School of Engineering Science, Osaka University, Toyonaka, Osaka
• 著者所属(英): en
• 著者所属(英): Division of Systems Science, Graduate School of Engineering Science, Osaka University, Toyonaka, Osaka
• 著者所属(英): en
• 著者所属(英): Division of Systems Science, Graduate School of Engineering Science, Osaka University, Toyonaka, Osaka
• 著者名: 間々田, 聡子; 牧野, 和久; 藤重, 悟
• 著者名(英): Satoko, Mamada; Kazuhisa, Makino; Satoru, Fujishige
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 本論文では，木構造ネットワークにおける動的フロー問題と施設配置問題を統合した問題を考察する．これは，木構造ネットワークと各点に供給量が与えられているとき，その全ての供給量を最速に輸送するような出口νを求める問題である．この問題は木構造ネットワークにおける１-センター問題の動的フロー版と見なすことができる．我々は，この施設配置問題に対するO(n2)時間アルゴリズムを与える．ただし，nはネットワークの点数である．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: In this paper we consider a compound problem of dynamic flows and sink location in a tree network. Given a dynamic flow network of tree structure with initial supplies at vertices, the problem is to find a vertex ν as a sink in the network such that we can send all the initial suplies to ν as quick as possible. This problem can be regarded as a dynamic flow version of the 1-centerin problem in a tree network. We present an O(n2) time algorithm for the sink location problem, where n is the number of vertices in the network.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 情報処理学会研究報告アルゴリズム（AL）; 巻 2001, 号 115(2001-AL-081), p. 35-42, 発行日 2001-11-27
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会