スパイダ被覆アルゴリズム: ネットワーク設計の最新理論

摘要

所望の制約を満たすネットワークの中でできるだけ低コストのものを求るネットワーク設計問題は，典型的なグラフ 最適化問題の一つである.故障に強い通信ネットワークを構築するのに役立つだけではなく，計算機科学の多岐にわたる 分野に応用を持つ.本稿では，ネットワーク設計問題に対する手法の一つであるスパイダ被覆アルゴリズムの基礎と最新 の研究動向を紹介する.