米山純央さん（理工学研究科 博士課程前期課程 2年生 情報科学専攻 巳波弘佳研究室）が2024年1月25日から26日にかけて熊本県で開催された電子情報通信学会コミュニケーションクオリティ研究会において「学生優秀発表賞」を受賞しました。

受賞した研究の概要は以下のとおりです。

【タイトル】
ノード保護による耐分断性の高いネットワーク設計問題に対する固定パラメータ容易性
【著者】
米山純央、巳波弘佳
【概要】
インターネットをはじめとする今や重要な社会インフラである情報ネットワークにおいては、ノードやリンクが自然災害やサイバー攻撃などによって故障が起こると被害の影響は極めて大きい。そのため、大規模な情報ネットワークのプロバイダにとって、リンクやノードの故障が発生した際にも通信が継続できるようにネットワークを構築することは重要な課題である。この課題に対処するために、「重要な」ノードやリンクのみを高信頼化（保護）することで、コストを抑えつつネットワーク全体の信頼性を高めるというアプローチが考えられる。そこで本研究では、高信頼化ノード以外のノードが故障しても、その後のネットワークで通信が継続できるようにするために最小限の個数の保護ノードを決定する設計問題を最適化問題として定式化した。この問題の数学的性質を調べ、この問題がNP困難の計算量クラスに属することを証明し、さらに同時故障ノード数の上限が定数ならば固定パラメータ容易性を持つことを証明した。