WEKO3
アイテム
独立同一分布の連続確率変数重みつきグラフ最適化問題における最適重み分布の#P-困難性
https://ipsj.ixsq.nii.ac.jp/records/241032
https://ipsj.ixsq.nii.ac.jp/records/24103232a621d4-9f25-4c9e-b18d-e368fe8b4724
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
IPSJ-AL24200016.pdf (957.6 kB)
2026年11月19日からダウンロード可能です。
|
Copyright (c) 2024 by the Information Processing Society of Japan
|
|
| 非会員：¥660, IPSJ:学会員：¥330, AL:会員：¥0, DLIB:会員：¥0 | ||
| Item type | SIG Technical Reports(1) | |||||||
|---|---|---|---|---|---|---|---|---|
| 公開日 | 2024-11-19 | |||||||
| タイトル | ||||||||
| タイトル | 独立同一分布の連続確率変数重みつきグラフ最適化問題における最適重み分布の#P-困難性 | |||||||
| タイトル | ||||||||
| 言語 | en | |||||||
| タイトル | #P-hardness of the Distribution of the Optimal Weight of the Graph Optimization in Graphs with i.i.d. Continuous Random Weight | |||||||
| 言語 | ||||||||
| 言語 | jpn | |||||||
| 資源タイプ | ||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_18gh | |||||||
| 資源タイプ | technical report | |||||||
| 著者所属 | ||||||||
| 専修大学 | ||||||||
| 著者名 |
安藤, 映
× 安藤, 映
|
|||||||
| 論文抄録 | ||||||||
| 内容記述タイプ | Other | |||||||
| 内容記述 | 閉路を持たない有向グラフの最長路問題および最短路問題を考える．辺の長さが確定的に与えられる場合にはこの問題はグラフ規模の線形時間で解くことができることが知られている．しかし，グラフの辺の長さが互いに独立で [0, 1] の上の一様分布に従う確率変数であると考えると，最長路や最短路の長さの分布を求める問題は高速な解法が知られていない．そこで本稿ではこの問題が #P- 困難であることを示す． | |||||||
| 書誌レコードID | ||||||||
| 収録物識別子タイプ | NCID | |||||||
| 収録物識別子 | AN1009593X | |||||||
| 書誌情報 |
研究報告アルゴリズム（AL） 巻 2024-AL-200, 号 16, p. 1-5, 発行日 2024-11-19 |
|||||||
| ISSN | ||||||||
| 収録物識別子タイプ | ISSN | |||||||
| 収録物識別子 | 2188-8566 | |||||||
| Notice | ||||||||
| SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc. | ||||||||
| 出版者 | ||||||||
| 言語 | ja | |||||||
| 出版者 | 情報処理学会 | |||||||
