「連結度増大問題」の版間の差分
ナビゲーションに移動
検索に移動
(新しいページ: ''''【れんけつどぞうだいもんだい (connectivity augmentation problem)】''' 与えられた無向(有向)グラフの辺連結度, あるいは点連結度を指...') |
Albeit-Kun (トーク | 投稿記録) |
||
| (他の1人の利用者による、間の1版が非表示) | |||
| 2行目: | 2行目: | ||
与えられた無向(有向)グラフの辺連結度, あるいは点連結度を指定された目標値まで大きくするためにグラフに最小費用の辺の集合を付加する問題である. この問題は一般にはNP困難であるが, 付加辺の本数を最小にする場合には, 以下の問題に対して多項式時間の解法が知られている. %無向グラフの各点対間の局所辺連結度をそれぞれの目標値まで上げる問題, 無向(有向)グラフの辺連結度を目標値まで上げる問題, 無向グラフの点連結度を4以下の目標値に上げる問題, 有向グラフの点連結度を1だけ上げる問題. | 与えられた無向(有向)グラフの辺連結度, あるいは点連結度を指定された目標値まで大きくするためにグラフに最小費用の辺の集合を付加する問題である. この問題は一般にはNP困難であるが, 付加辺の本数を最小にする場合には, 以下の問題に対して多項式時間の解法が知られている. %無向グラフの各点対間の局所辺連結度をそれぞれの目標値まで上げる問題, 無向(有向)グラフの辺連結度を目標値まで上げる問題, 無向グラフの点連結度を4以下の目標値に上げる問題, 有向グラフの点連結度を1だけ上げる問題. | ||
| + | |||
| + | [[Category:グラフ･ネットワーク|れんけつどぞうだいもんだい]] | ||
2008年11月14日 (金) 09:47時点における最新版
【れんけつどぞうだいもんだい (connectivity augmentation problem)】
与えられた無向(有向)グラフの辺連結度, あるいは点連結度を指定された目標値まで大きくするためにグラフに最小費用の辺の集合を付加する問題である. この問題は一般にはNP困難であるが, 付加辺の本数を最小にする場合には, 以下の問題に対して多項式時間の解法が知られている. %無向グラフの各点対間の局所辺連結度をそれぞれの目標値まで上げる問題, 無向(有向)グラフの辺連結度を目標値まで上げる問題, 無向グラフの点連結度を4以下の目標値に上げる問題, 有向グラフの点連結度を1だけ上げる問題.