辞書式最適最速到達フロー問題

• Item type: SIG Technical Reports(1)
• 公開日: 2018-08-27
• タイトル: 辞書式最適最速到達フロー問題
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 九州大学／JSTさきがけ
• 著者名: 神山, 直之
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: Ford & Fulkerson によって提案された動的ネットワークとは，各辺が容量と移動時間を持つ有向グラフである．動的ネットワーク上の基本的な問題の一つとして避難計画問題がある．この問題の目的は，全てのサプライをシンクまで最も早く流すことのできる動的ネットワーク上の動的フローを求めることである．最速到達フローとは，全ての時刻においてシンクへ到達しているサプライの量を最大化する避難計画問題の解である．シンクの数が 1 つの場合は，最速到達フローが常に存在することが知られている．しかし，シンクが 2 つ以上存在しシンクに容量がある場合は，最速到達フローが存在しない問題例が存在することが知られている．本論文では，この非存在性を回避するために，複数のシンクを持つ動的ネットワークにおける新たな解として辞書式最適最速到達フローを提案する．この解は，Megiddo が提案した通常のネットワークフローにおける辞書式最適フローから発想を得たものである．本論文では，一般の動的ネットワークにおける辞書式最適最速到達フローを求める擬多項式時間アルゴリズムを提案する．さらに，全ての辺の移動時間が 0 の場合に対する多項式時間アルゴリズムを提案する．
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 研究報告アルゴリズム（AL）; 巻 2018-AL-169, 号 9, p. 1-2, 発行日 2018-08-27
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 2188-8566
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会