小特集　グラフアルゴリズムの最先端 9. スパイダ被覆アルゴリズム――ネットワーク設計の最新理論―― Spider Covering Algorithm:Recent Progress of Network Design

pp280
福永拓郎

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