WEKO3
アイテム
格子状の動的フローネットワークにおける避難施設配置問題
https://ipsj.ixsq.nii.ac.jp/records/222158
https://ipsj.ixsq.nii.ac.jp/records/222158b3059296-51a7-405a-9171-f6479b19b803
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
IPSJ-AL22190019.pdf (1.0 MB)
|
Copyright (c) 2022 by the Information Processing Society of Japan
|
|
| オープンアクセス | ||
| Item type | SIG Technical Reports(1) | |||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 公開日 | 2022-11-10 | |||||||||||||
| タイトル | ||||||||||||||
| タイトル | 格子状の動的フローネットワークにおける避難施設配置問題 | |||||||||||||
| 言語 | ||||||||||||||
| 言語 | jpn | |||||||||||||
| 資源タイプ | ||||||||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_18gh | |||||||||||||
| 資源タイプ | technical report | |||||||||||||
| 著者所属 | ||||||||||||||
| 兵庫県立大学社会情報科学部社会情報科学科 | ||||||||||||||
| 著者所属 | ||||||||||||||
| 兵庫県立大学大学院情報科学研究科 | ||||||||||||||
| 著者所属 | ||||||||||||||
| 兵庫県立大学大学院情報科学研究科 | ||||||||||||||
| 著者所属 | ||||||||||||||
| 兵庫県立大学大学院情報科学研究科 | ||||||||||||||
| 著者名 |
西井, 彩乃
× 西井, 彩乃
× 照山, 順一
× 戸國, 友貴
× 東川, 雄哉
|
|||||||||||||
| 論文抄録 | ||||||||||||||
| 内容記述タイプ | Other | |||||||||||||
| 内容記述 | 動的フローネットワークは，各頂点に避難者数を示す供給量，各辺に容量と移動時間が与えられた有向グラフで定義される．動的フローネットワークの頂点上あるいは辺上に避難施設を配置すると，すべての避難者が避難施設に到着可能な最小時間，すなわち避難完了時間が定義できる．避難施設配置問題とは，避難完了時間を最小化する施設の配置を求める問題である．この問題については，これまでパス，木，サイクルなど限定されたネットワークに対してのみ多項式時間アルゴリズムが知られているが，より複雑なネットワークに対しては多項式時間アルゴリズムが知られていない．本稿では，辺の容量と移動時間が一定である格子状のネットワークについて，単一施設配置問題が多項式時間で解けることを示した． | |||||||||||||
| 書誌レコードID | ||||||||||||||
| 収録物識別子タイプ | NCID | |||||||||||||
| 収録物識別子 | AN1009593X | |||||||||||||
| 書誌情報 |
研究報告アルゴリズム（AL） 巻 2022-AL-190, 号 19, p. 1-6, 発行日 2022-11-10 |
|||||||||||||
| ISSN | ||||||||||||||
| 収録物識別子タイプ | ISSN | |||||||||||||
| 収録物識別子 | 2188-8566 | |||||||||||||
| Notice | ||||||||||||||
| SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc. | ||||||||||||||
| 出版者 | ||||||||||||||
| 言語 | ja | |||||||||||||
| 出版者 | 情報処理学会 | |||||||||||||
