2024-03-28T14:08:03Z
https://niigata-u.repo.nii.ac.jp/oai
oai:niigata-u.repo.nii.ac.jp:00003309
2022-12-15T03:36:26Z
423:424:425
453:454
Realization of an Undirected Flow Network from a Subset of the Set of the Maximum Flow Values (Terminal Capacities) between Every Pair of Vertices
一部の最大流量からの無向フローネットワークの実現
一部の最大流量からの無向フローネットワークの実現
田村, 裕
42004
仙石, 正和
42005
篠田, 庄司
5445
阿部, 武雄
42007
ある点集合において,すべての2点間の最大流量を与え,それらが無向フローネットワーク上に実現できるかどうかの判定や,実際にフローネットワークを構成する問題については多くの研究がなされている.ところで,輸送網などを設計する際には,すべての都市間ではなく一部の重要都市間の輸送量のみが満足されることが要求される場合がある.そこで本論文では,一部の最大流量を与えた場合の無向フローネットワーク上への実現について論ずる.まず無向フローネットワーク上へ実現できるかどうかの判定アルゴリズムを与えるが,これは,これまでに得られている結果を補足的に拡張したものとなっている.次に,一部の最大流量を与えた時点で自動的に決定してしまう,与えられた以外の最大流量を求める問題について考察し,そのアルゴリズムを与える.そして,このアルゴリズムに用いる簡易化ネットワークを構成することで,与えられた最大流量から不要なものを除くことが可能であり,この問題を最短絡問題に帰着させることが可能であることを示している.
journal article
電子情報通信学会
1989-08
application/pdf
電子情報通信学会論文誌. A, 基礎・境界
8
J72-A
1316
1326
電子情報通信学会論文誌. A, 基礎・境界
AN10013345
09135707
https://niigata-u.repo.nii.ac.jp/record/3309/files/J72-A_8_1316-1326.pdf
jpn
http://www.ieice.org/jpn/trans_online/
copyright(C)1989 IEICE