| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 2023-10-07 13:00 指定の頂点数と次数の下で代数的連結度を最大にする正則グラフの探索アルゴリズム ○倉橋正司・右田剛史・高橋規一（岡山大）  CAS2023-54 NLP2023-53 |
|
| 抄録 | （和） | 代数的連結度はネットワークの堅牢性を表す指標の1つであり，ラプラシアン行列の2番目に小さい固有値で定義される．したがって，代数的連結度を最大にするグラフを求めることは，攻撃や故障に耐性のあるネットワークの構築に関わる重要な問題である．しかしながら，例えば頂点数と辺数のみが指定されている場合でも，グラフの代数的連結度はその接続構造によって大きく変化し，また条件を満たすグラフの数は膨大であるため，代数的連結度が最大のものを見つけるのは困難である．そこで本報告では，すべての頂点の次数が等しい正則グラフに焦点を当て，指定の頂点数と次数の下で代数的連結度を最大にする正則グラフを求める問題を考える．この問題に対して，深さ優先探索に枝刈りを導入したアルゴリズムを提案し，その有効性を実験的に評価する．提案アルゴリズムは，ポート数が同一である多数のスイッチをLANケーブルで接続して堅牢な計算機ネットワークを構築するのに利用できる． |
| （英） | Algebraic connectivity is a measure of network robustness, and defined by the second smallest eigenvalue of the Laplacian matrix of the graph. Therefore, finding a graph that maximizes the algebraic connectivity is an important problem in constructing networks that are resilient to attacks and failures. However, even when only the number of vertices and edges are specified, the algebraic connectivity of a graph varies greatly depending on its structure, and the number of graphs satisfying the condition is huge. It is thus difficult to find a graph with the largest algebraic connectivity. In this report, we focus on regular graphs where the degree of all vertices is equal, and consider the problem of finding a regular graph that maximizes the algebraic connectivity under a specified number of vertices and degree. For this problem, we propose a depth-first search algorithm with some pruning techniques, and evaluate its effectiveness experimentally. The proposed algorithm can be used to construct a robust computer network consisting of many switches with the same number of ports. | |
| キーワード | （和） | 代数的連結度 / ラプラシアン行列 / 正則グラフ / 深さ優先探索 / 枝刈り / / / |
| （英） | algebraic connectivity / Laplacian matrix / regular graphs / depth-first search / pruning / / / | |
| 文献情報 | 信学技報, vol. 123, no. 203, NLP2023-53, pp. 106-110, 2023年10月. | |
| 資料番号 | NLP2023-53 | |
| 発行日 | 2023-09-29 (CAS, NLP) | |
| ISSN | Online edition: ISSN 2432-6380 | |
| 著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します．(許諾番号：10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| PDFダウンロード | CAS2023-54 NLP2023-53 |
|
| 研究会情報 | |
| 研究会 | NLP CAS |
| 開催期間 | 2023-10-06 - 2023-10-07 |
| 開催地（和） | ワークプラザ岐阜 |
| 開催地（英） | Work plaza Gifu |
| テーマ（和） | CAS, NLP, 一般 |
| テーマ（英） | CAS, NLP, etc. |
| 講演論文情報の詳細 | |
| 申込み研究会 | NLP |
| 会議コード | 2023-10-NLP-CAS |
| 本文の言語 | 日本語 |
| タイトル（和） | 指定の頂点数と次数の下で代数的連結度を最大にする正則グラフの探索アルゴリズム |
| サブタイトル（和） | |
| タイトル（英） | An algorithm for finding regular graphs that maximize algebraic connectivity under a specified number of vertices and degree |
| サブタイトル（英） | |
| キーワード(1)（和/英） | 代数的連結度 / algebraic connectivity |
| キーワード(2)（和/英） | ラプラシアン行列 / Laplacian matrix |
| キーワード(3)（和/英） | 正則グラフ / regular graphs |
| キーワード(4)（和/英） | 深さ優先探索 / depth-first search |
| キーワード(5)（和/英） | 枝刈り / pruning |
| キーワード(6)（和/英） | / |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第1著者 氏名（和/英/ヨミ） | 倉橋 正司 / Masashi Kurahashi / クラハシ マサシ |
| 第1著者 所属（和/英） | 岡山大学 (略称： 岡山大) Okayama University (略称： Okayama Univ.) |
| 第2著者 氏名（和/英/ヨミ） | 右田 剛史 / Tsuyoshi Migita / ミギタ ツヨシ |
| 第2著者 所属（和/英） | 岡山大学 (略称： 岡山大) Okayama University (略称： Okayama Univ.) |
| 第3著者 氏名（和/英/ヨミ） | 高橋 規一 / Norikazu Takahashi / タカハシ ノリカズ |
| 第3著者 所属（和/英） | 岡山大学 (略称： 岡山大) Okayama University (略称： Okayama Univ.) |
| 講演者 | 第1著者 |
| 発表日時 | 2023-10-07 13:00:00 |
| 発表時間 | 20分 |
| 申込先研究会 | NLP |
| 資料番号 | CAS2023-54, NLP2023-53 |
| 巻番号（vol） | vol.123 |
| 号番号（no） | no.202(CAS), no.203(NLP) |
| ページ範囲 | pp.106-110 |
| ページ数 | 5 |
| 発行日 | 2023-09-29 (CAS, NLP) |
[研究会発表申込システムのトップページに戻る]