| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 2019-10-10 16:10 ［招待講演］二分決定グラフを用いたネットワーク信頼性計算の最近の動向 ○川原 純（京大）  NS2019-113 |
|
| 抄録 | （和） | ネットワーク信頼性評価とは，ネットワークの各リンクに静的な故障確率が与えられた際に，指定された2点間が通信可能となる確率を求める基礎的な問題であり，1970年代以前から研究が進められている．確率の厳密値を計算する手法として，二分決定グラフ（BDD）を用いた手法が高速であることが知られている．近年，BDDを用いて，与えられたグラフの全域木やパス，マッチング等を高速に列挙する技法が開発され，例えば，一票の格差の小さな選挙区割を求める問題や，避難所割当問題等のグラフに関する最適化問題に応用されている．本講演では，それらのグラフ最適化問題を解く新しい技法を，古くからあるネットワーク信頼性評価に適用して，リンク故障の依存関係や，ノード故障を考慮した信頼性評価を行う手法について論じる． |
| （英） | Given a network with static link failure probabilities, the network reliability is to compute the probability that two specified nodes are communicable. The problem is one of the most fundamental problems in the field of networking and has been widely studied since the 1970's. It is known that a method based on binary decision diagrams (BDDs) strictly computes the probability fast. Recently, algorithms for enumerating spanning trees, paths and matchings of a given graph using BDDs have been developed and they have been applied to graph optimization problems such as evacuation planning and obtaining electoral districts with small disparity. In this research, it is shown that the traditional network reliability in situations that the network has link dependencies or node failures may occur can be efficiently computed by making use of these techniques for graph optimization problems. | |
| キーワード | （和） | ネットワーク信頼性評価 / 二分決定グラフ / グラフアルゴリズム / グラフ列挙 / ノード故障 / / / |
| （英） | Network reliability / Binary decision diagram / Graph algorithm / Graph enumeration / Node failure / / / | |
| 文献情報 | 信学技報, vol. 119, no. 221, NS2019-113, pp. 59-62, 2019年10月. | |
| 資料番号 | NS2019-113 | |
| 発行日 | 2019-10-03 (NS) | |
| ISSN | Online edition: ISSN 2432-6380 | |
| 著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します．(許諾番号：10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| PDFダウンロード | NS2019-113 |
|
| 研究会情報 | |
| 研究会 | NS |
| 開催期間 | 2019-10-10 - 2019-10-11 |
| 開催地（和） | 名古屋工業大学 |
| 開催地（英） | Nagoya Institute of Technology |
| テーマ（和） | ネットワークアーキテクチャ(オーバレイ，P2P，ユビキタスNW，スケールフリーNW，アクティブNW，NGN・新世代NW，IoT，エッジコンピューティング)，次世代パケットトランスポート(高速Ethernet，IP over WDM，マルチサービスパケット技術，MPLS)，グリッド，一般 |
| テーマ（英） | Network architecture (Overlay, P2P, Ubiquitous network, Scale-free network, Active network, NGN/NwGN, IoT, Edge computing, Next generation packet transport (High speed Ethernet, IP over WDM, Multi-service package technology, MPLS), Grid, etc. |
| 講演論文情報の詳細 | |
| 申込み研究会 | NS |
| 会議コード | 2019-10-NS |
| 本文の言語 | 日本語 |
| タイトル（和） | 二分決定グラフを用いたネットワーク信頼性計算の最近の動向 |
| サブタイトル（和） | |
| タイトル（英） | On recent developments in network reliability computation using binary decision diagrams |
| サブタイトル（英） | |
| キーワード(1)（和/英） | ネットワーク信頼性評価 / Network reliability |
| キーワード(2)（和/英） | 二分決定グラフ / Binary decision diagram |
| キーワード(3)（和/英） | グラフアルゴリズム / Graph algorithm |
| キーワード(4)（和/英） | グラフ列挙 / Graph enumeration |
| キーワード(5)（和/英） | ノード故障 / Node failure |
| キーワード(6)（和/英） | / |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第1著者 氏名（和/英/ヨミ） | 川原 純 / Jun Kawahara / カワハラ ジュン |
| 第1著者 所属（和/英） | 京都大学 (略称： 京大) Kyoto University (略称： Kyoto Univ.) |
| 講演者 | 第1著者 |
| 発表日時 | 2019-10-10 16:10:00 |
| 発表時間 | 45分 |
| 申込先研究会 | NS |
| 資料番号 | NS2019-113 |
| 巻番号（vol） | vol.119 |
| 号番号（no） | no.221 |
| ページ範囲 | pp.59-62 |
| ページ数 | 4 |
| 発行日 | 2019-10-03 (NS) |
[研究会発表申込システムのトップページに戻る]