min-cost connectivity problem のサーベイ
大学院生の頃、グラフ連結度周辺の研究をしていた時期があって、今でもたまに文献を読む。
Nutov というグラフ連結度に関するアルゴリズムが専門の研究者がいて、サーベイを自身のサイトに上げていたのだが、最近アップデートされていた。リンクを貼る。
Node-Connectivity Survivable Network Problems,
http://www.openu.ac.il/home/nutov/SN.pdf
MEMO: 最小スパニング木問題、巡回セールスマン問題、及び最小スタイナー木問題等の共通の一般化として、サバイバルネットワーク問題とよばれるものがあるのだがそのサーベイ。
The k-Connected Subgraph Problem
http://www.openu.ac.il/home/nutov/kCS.pdf
MEMO: 辺重みつきのグラフ G が与えられたとき、k連結であるような G の部分グラフを算出する問題を k 連結部分グラフ問題とよび、そのサーベイ。辺重みのつけ方で問題を分類している。