| Item type |
学術雑誌論文 / Journal Article(1) |
| 公開日 |
2012-08-07 |
| タイトル |
|
|
タイトル |
フローネットワークの出口配置問題 |
|
言語 |
ja |
| タイトル |
|
|
タイトル |
Problems of Where to Locate p-Sinks in a Flow Network |
|
言語 |
en |
| 言語 |
|
|
言語 |
jpn |
| キーワード |
|
|
主題 |
フローネットワーク |
| キーワード |
|
|
主題 |
ロケーション問題 |
| キーワード |
|
|
主題 |
疑多項式時間アルゴリズム |
| キーワード |
|
|
主題 |
動的計画法 |
| 資源タイプ |
|
|
資源タイプ識別子 |
http://purl.org/coar/resource_type/c_6501 |
|
資源タイプ |
journal article |
| 著者 |
渡辺, 郁
田村, 裕
仙石, 正和
|
| 抄録 |
|
|
内容記述タイプ |
Abstract |
|
内容記述 |
フローネットワークのロケーション問題として,p-センター問題やp-メジアン問題があり,それらは多項式時間で解けることが知られている.本論文では,フローネットワークの新たな一つのロケーション問題を提案する.それは一つの固定された入口とp個の(固定されていない)出口をもつフローネットワークNを考え,Nに最大フローが最大になるようにp個の出口をうまく配置する問題である(この問題をp-回収問題と呼ぶ).まず木状ネットワークに対する1-回収問題を解く線形時間アルゴリズム,次に動的計画法に基づいた木状ネットワークのp-回収時間を解く疑多項式時間アルゴリズムを与える.また木状ネットワークに対する1-回収問題に対応する判定問題はNP-完全であることが知られているので,その判定問題が強NP-完全でないことがわかる. |
| 書誌情報 |
電子情報通信学会論文誌. A, 基礎・境界
巻 78,
号 8,
p. 938-946,
発行日 1995-08
|
| ISSN |
|
|
収録物識別子タイプ |
ISSN |
|
収録物識別子 |
0913-5707 |
| 書誌レコードID |
|
|
収録物識別子タイプ |
NCID |
|
収録物識別子 |
AN10013345 |
| 権利 |
|
|
権利情報 |
Copyright(C)1995IEICE(許諾番号11MB0126） |
| 著者版フラグ |
|
|
出版タイプ |
VoR |
|
出版タイプResource |
http://purl.org/coar/version/c_970fb48d4fbd8a85 |
| 出版者 |
|
|
出版者 |
電子情報通信学会 |
| 関係URI |
|
|
|
関連名称 |
http://search.ieice.org/ |
j78-a_8_938.pdf (517 KB)
