| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 2025-09-04 10:20 二分決定グラフによるヒッティングセット演算の拡張とネットワーク信頼性評価への応用 ○西澤恭祐（奈良高専）・中畑 裕・笠原正治（奈良先端大）・山口賢一（奈良高専）  COMP2025-4 |
|
| 抄録 | （和） | ネットワーク信頼性評価とは，ネットワーク内の各リンクが独立に静的な確率で故障する場合に，指定された頂点対が接続されている確率を求める問題である．本研究では，与えられたグラフにおいて各リンクが一定の確率で故障する場合に，全頂点対が$k$辺連結である確率を計算する新たな手法を提案する． 既存研究では，DisjointJoin演算と呼ばれる演算を用いてこの問題に対処する手法が提案されているが，DisjointJoinは入力となるZDDのサイズに対して指数時間の計算量を要することが知られている． 本研究の提案手法では，まず与えられたグラフに対して，そのカットセットを表現するゼロサプレス型二分決定図（ZDD）を構築し，次に新たに提案する$k$-ヒッティングセット演算を適用することで，条件を満たす部分グラフ族を表す二分決定図（BDD）またはZDDを生成し確率を計算する. |
| （英） | Network reliability evaluation is the problem of computing the probability that a specified pair of nodes is connected, assuming that each link in the network fails independently with a static probability. In this study, we propose a novel method for computing the probability that all pairs of nodes in a given graph are $k$-edge-connected, assuming each link fails with a fixed probability. Previous research has addressed this problem using an operation called DisjointJoin, however it is known that DisjointJoin requires exponential time with respect to the size of the input Zero-suppressed Binary Decision Diagram (ZDD). In our proposed method, we first construct a ZDD that represents the cut sets of the given graph. Then, by applying a newly proposed $k$-hitting set operation, we generate a Binary Decision Diagram (BDD) or ZDD that represents the family of subgraphs satisfying the k-edge-connectivity condition. Finally, we compute the desired probability from this representation. |
|
| キーワード | （和） | BDD/ZDD / ネットワーク信頼性評価 / k辺連結 / / / / / |
| （英） | BDD/ZDD / Network Reliability Evaluation / k-Edge-Connected / / / / / | |
| 文献情報 | 信学技報, vol. 125, no. 175, COMP2025-4, pp. 1-7, 2025年9月. | |
| 資料番号 | COMP2025-4 | |
| 発行日 | 2025-08-28 (COMP) | |
| ISSN | Online edition: ISSN 2432-6380 | |
| 著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します．(許諾番号：10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| PDFダウンロード | COMP2025-4 |
|
| 研究会情報 | |
| 研究会 | COMP IPSJ-AL |
| 開催期間 | 2025-09-04 - 2025-09-05 |
| 開催地（和） | 北海道科学大学 |
| 開催地（英） | Hokkaido University of Science |
| テーマ（和） | 理論計算機科学，一般 |
| テーマ（英） | Theoretical Computer Science, etc. |
| 講演論文情報の詳細 | |
| 申込み研究会 | COMP |
| 会議コード | 2025-09-COMP-AL |
| 本文の言語 | 日本語 |
| タイトル（和） | 二分決定グラフによるヒッティングセット演算の拡張とネットワーク信頼性評価への応用 |
| サブタイトル（和） | |
| タイトル（英） | Extension of Hitting Set Operations Using Binary Decision Diagrams and Their Application to Network Reliability Evaluation |
| サブタイトル（英） | |
| キーワード(1)（和/英） | BDD/ZDD / BDD/ZDD |
| キーワード(2)（和/英） | ネットワーク信頼性評価 / Network Reliability Evaluation |
| キーワード(3)（和/英） | k辺連結 / k-Edge-Connected |
| キーワード(4)（和/英） | / |
| キーワード(5)（和/英） | / |
| キーワード(6)（和/英） | / |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第1著者 氏名（和/英/ヨミ） | 西澤 恭祐 / Kyosuke Nishizawa / ニシザワ キョウスケ |
| 第1著者 所属（和/英） | 奈良工業高等専門学校 (略称： 奈良高専) National Institute of Technology, Nara College (略称： NITNC) |
| 第2著者 氏名（和/英/ヨミ） | 中畑 裕 / Yu Nakahata / ナカハタ ユウ |
| 第2著者 所属（和/英） | 奈良先端科学技術大学院大学 (略称： 奈良先端大) Nara Institute of Science and Technology (略称： NAIST) |
| 第3著者 氏名（和/英/ヨミ） | 笠原 正治 / Shoji Kasahara / カサハラ ショウジ |
| 第3著者 所属（和/英） | 奈良先端科学技術大学院大学 (略称： 奈良先端大) Nara Institute of Science and Technology (略称： NAIST) |
| 第4著者 氏名（和/英/ヨミ） | 山口 賢一 / Kenichi Yamaguchi / ヤマグチ ケンイチ |
| 第4著者 所属（和/英） | 奈良工業高等専門学校 (略称： 奈良高専) National Institute of Technology, Nara College (略称： NITNC) |
| 講演者 | 第1著者 |
| 発表日時 | 2025-09-04 10:20:00 |
| 発表時間 | 25分 |
| 申込先研究会 | COMP |
| 資料番号 | COMP2025-4 |
| 巻番号（vol） | vol.125 |
| 号番号（no） | no.175 |
| ページ範囲 | pp.1-7 |
| ページ数 | 7 |
| 発行日 | 2025-08-28 (COMP) |
[研究会発表申込システムのトップページに戻る]