| 講演名 | 1993/5/27 確率付グラフ上の辺素なs-t路の期待最大本数の下界値 程 鵬, 増山 繁, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | 確率付グラフ(G,p)を考える。ただし、Gは指定された2つの節点、ソースsとシンクtを持つ2端子無向グラフであり、pはGの各辺の故障確率のベクトルである。ここで、各辺の故障(すなわち、故障を切断として扱う)が独立に生起し、各節点が故障しないことを仮定する。確率付グラフ(G,p)上の辺素なs-t路の期待最大本数を計算する問題はグラフGを平面グラフやs-t出入双木やs-t完全多段グラフなどに限定してもNP困難であることが既に知られている。従って、その期待最大本数を評価する手法として、その期待最大本数の下界値を計算する方法が望まれる。本論文では、確率付グラフ(G,p)において、各s-t路にs-t路番号を与えることによって計算される、その期待最大本数の一つの下界値を提案する。この提案した下界値が期待最大本数と等しくなるための必要十分条件、すなわち、グラフの特徴づけを明らかにする。 |
| 抄録(英) | For a probabilistic graph(G=(V,E,s,t),p),where G is an undirected graph with specifed source vertex s and sink vertex t(s≠ t)in which each edge has independent failure probability and each vertex is assumed to be failure-free,and p=(p(e_1),…,p(e_ E >)) i s a vector consisting of failure probabilities p(e_i)′s of all edg es e_i′s in E,we consider the problem of computing the expected ma ximum number Γ_(G,p)> of edge-disjoint s-t paths.It has been know n that this computing problem is NP-hard even if G is restricted to several classes like planar graphs,s-t out-in bitrees and s-t complete multi-stage graphs.In this paper,for a probabilistic graph (G=(V,E,s,t),p),we propose a lower bound of Γ_(G,p)> and sh ow the necessary and sufficient conditions by which the lower bound coincides with Γ_(G,p)>. |
| キーワード(和) | 確率付グラフ / 辺素なs-t路 / 辺素なs-t路の期待最大本数 / 下界値 / NP困難 |
| キーワード(英) | probabilistic graph / edge-diejoint s-t paths / expected maximum number of edge-diejoint s-t paths / lower bourd / NP-hard |
| 資料番号 | COMP93-7,SS93-1 |
| 発行日 |
| 研究会情報 | |
| 研究会 | COMP |
|---|---|
| 開催期間 | 1993/5/27(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Theoretical Foundations of Computing (COMP) |
|---|---|
| 本文の言語 | ENG |
| タイトル（和） | 確率付グラフ上の辺素なs-t路の期待最大本数の下界値 |
| サブタイトル（和） | |
| タイトル（英） | A Lower Bound of the Expected Maximum Number of Edge-disjoint s-t Paths on Probabilistic Graphs |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 確率付グラフ / probabilistic graph |
| キーワード(2)（和/英） | 辺素なs-t路 / edge-diejoint s-t paths |
| キーワード(3)（和/英） | 辺素なs-t路の期待最大本数 / expected maximum number of edge-diejoint s-t paths |
| キーワード(4)（和/英） | 下界値 / lower bourd |
| キーワード(5)（和/英） | NP困難 / NP-hard |
| 第 1 著者 氏名（和/英） | 程 鵬 / Peng Cheng |
| 第 1 著者 所属（和/英） | 豊橋技術科学大学 Toyohashi University of Technology |
| 第 2 著者 氏名（和/英） | 増山 繁 / Shigeru Masuyama |
| 第 2 著者 所属（和/英） | 豊橋技術科学大学 Toyohashi University of Technology |
| 発表年月日 | 1993/5/27 |
| 資料番号 | COMP93-7,SS93-1 |
| 巻番号（vol） | vol.93 |
| 号番号（no） | 81 |
| ページ範囲 | pp.- |
| ページ数 | 8 |
| 発行日 | |