正需要に対してBraessパラドックスが起こり得ない2連結無向多品種グラフの判定

• Item type: SIG Technical Reports(1)
• 公開日: 2024-11-19
• タイトル: 正需要に対してBraessパラドックスが起こり得ない2連結無向多品種グラフの判定
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 金沢大学大学院電子情報通信学専攻
• 著者所属: 金沢大学大学院電子情報通信学専攻
• 著者名: 神林, 晃士郎; 松林, 昭
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: Braess パラドックスとは，いくつかの品種，各品種の需要量，ならびに各辺のコスト関数が定められているグラフに対して，辺の削除がナッシュフローのコストを減少させるという，直感に反する望ましくない現象である．ここで，1つ の品種はグラフ上の供給点と需要点の対からなり，需要量は供給点から需要点への要求フロー量を表す正の数である．これまで，与えられた有向または無向グラフと k 個の品種が Braess パラドックスに対して脆弱でない，すなわち，任意の辺コスト関数と任意の需要量に対して Braess パラドックスが起こらないか否かを判定する多項式時間アルゴリズムが知られている．しかし，このアルゴリズムが基にしている脆弱なグラフの特徴付けは 0 の需要量が許容されることを前提としており，実際，k - 2 個の品種に対して需要量を 0 に設定することにより，実質的に k = 2 の場合に帰着している．これまで，任意の辺コスト関数と任意の正の需要量に対して Braess パラドックスが起こらないような 3 個以上の品種を持つグラフの特徴付けは知られていない．本報告では，グラフが無向 2 重連結であり，1 個以上の品種を持つとき，任意の辺コスト関数と任意の正の需要量に対して Braess パラドックスが起こらないための線形時間で判定可能な必要十分条件を示す．この特徴付けは，より精密な Braess パラドックスの検出，すなわち，与えられた無向 2 重連結グラフ，k 個以上の品種 (k ≧ 1)，正の需要量に対して，どのような辺コスト関数でも Braess パラドックスが起こらないか否かを判定するためにも利用できる．
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 研究報告アルゴリズム（AL）; 巻 2024-AL-200, 号 26, p. 1-8, 発行日 2024-11-19
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 2188-8566
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会