テイ ホウ   Cheng Peng
  程 鵬
   所属   経営学部
   職種   教授
言語種別 英語
発行・発表の年月 1995
形態種別 研究論文（学術雑誌）
査読 査読あり
標題 A Lower Bound of the Expected Maximum Number of Edge-Disjoint s-t Paths in Probabilistic Graphs
執筆形態 共著
掲載誌名 Discrete Applied Mathematics
掲載区分国外
巻・号・頁 Vol. 56(No. 2),pp.137-155
担当区分 筆頭著者,最終著者,責任著者
著者・共著者 Shigeru Masuyama
概要 本論文は、確率付きグラフにおいて、2節点間の辺素な路の最大本数の期待値を計算する問題がNP困難であることが知られている。本論文は、まずその下界値を求めるアルゴリズムを提案し、そしてこのアルゴリズムによって求めた下界値を真の期待値と一致するための必要十分条件を示したものである。