連結度増大問題

【れんけつどぞうだいもんだい (connectivity augmentation problem)】

与えられた無向(有向)グラフの辺連結度, あるいは点連結度を指定された目標値まで大きくするためにグラフに最小費用の辺の集合を付加する問題である. この問題は一般にはNP困難であるが, 付加辺の本数を最小にする場合には, 以下の問題に対して多項式時間の解法が知られている. %無向グラフの各点対間の局所辺連結度をそれぞれの目標値まで上げる問題, 無向(有向)グラフの辺連結度を目標値まで上げる問題, 無向グラフの点連結度を4以下の目標値に上げる問題, 有向グラフの点連結度を1だけ上げる問題.