Tadachika Oki の日記

私の日々の雑感です。https://sites.google.com/site/tadachikaoki0/

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 連結部分グラフ問題とよび、そのサーベイ。辺重みのつけ方で問題を分類している。