| 講演名 | 1993/12/15 辺の長さを持つグラフに対する各辺を通る最短路本数の計算問題 程 鵬, 増山 繁, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | 各辺が実数の長さを持つ有向グラフG=(V,E)に対して、指定された節点sから他の各節点への(又は、すべての節点間の)すべての最短路の中で、ある辺e(∈E)を通る最短路の本数をその辺の重みw_s(e)(又は、w(e))として定義する。本論文では、長さが零あるいは負である有向閉路を持たない有向グラフに対して、各辺e(∈E)の重みW_s(e)(又は、w(e))を求める多項式時間アルゴリズムを提案する。このアルゴリズムは各辺が正実数の長さを持つ無向グラフに対しても有効である。 |
| 抄録(英) | This paper considers a directed graph where each edge is assigned a real number,called length.We propose polynomial time algorithms for computing the weight of each edge to be defined as the numbers of shortest paths passing the edge from a specified source s to every other vertex and between all vertex pairs, respectively,for a directed graph with neither cycle of negative length nor cycle of length zero.Furthermore,it is shown that proposed algorithms are also valid for an undirected graph with each edge having a positive length. |
| キーワード(和) | グラフ理論 / 最短路 / 多項式時間アルゴリズム |
| キーワード(英) | Graph Theory / shortest path / polynomial time algorithm |
| 資料番号 | COMP93-62 |
| 発行日 |
| 研究会情報 | |
| 研究会 | COMP |
|---|---|
| 開催期間 | 1993/12/15(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Theoretical Foundations of Computing (COMP) |
|---|---|
| 本文の言語 | ENG |
| タイトル（和） | 辺の長さを持つグラフに対する各辺を通る最短路本数の計算問題 |
| サブタイトル（和） | |
| タイトル（英） | Computing the Weights of Edges with Respect to Shortest Paths in a Graph |
| サブタイトル（和） | |
| キーワード(1)（和/英） | グラフ理論 / Graph Theory |
| キーワード(2)（和/英） | 最短路 / shortest path |
| キーワード(3)（和/英） | 多項式時間アルゴリズム / polynomial time algorithm |
| 第 1 著者 氏名（和/英） | 程 鵬 / Peng Cheng |
| 第 1 著者 所属（和/英） | 豊橋技術科学大学知識情報工学係 Department of Knowledge-Based Information Engineering,Toyohashi University of Technology |
| 第 2 著者 氏名（和/英） | 増山 繁 / Shigeru Masuyama |
| 第 2 著者 所属（和/英） | 豊橋技術科学大学知識情報工学係 Department of Knowledge-Based Information Engineering,Toyohashi University of Technology |
| 発表年月日 | 1993/12/15 |
| 資料番号 | COMP93-62 |
| 巻番号（vol） | vol.93 |
| 号番号（no） | 379 |
| ページ範囲 | pp.- |
| ページ数 | 10 |
| 発行日 | |