スパイダ被覆アルゴリズム――ネットワーク設計の最新理論――
Vol.101 No.3pp.280-283
発行日:2018/03/01
Online ISSN:2188-2355
Print ISSN:0913-5693
種別:小特集 グラフアルゴリズムの最先端
専門分野:
キーワード:
組合せ最適化, ネットワーク設計, 連結度, グラフアルゴリズム,
本文:PDF(382.3KB)>>
あらまし:
所望の制約を満たすネットワークの中でできるだけ低コストのものを求めるネットワーク設計問題は,典型的なグラフ最適化問題の一つである.故障に強い通信ネットワークを構築するのに役立つだけではなく,計算機科学の多岐にわたる分野に応用を持つ.本稿では,ネットワーク設計問題に対する手法の一つであるスパイダ被覆アルゴリズムの基礎と最新の研究動向を紹介する.