次数増加禁止点を持つグラフの指定点集合に対する2, 3点連結化問題の解法
スポンサーリンク
概要
- 論文の詳細を見る
次数増加禁止点を持つグラフの指定点集合に対するk点連結化問題kVCA(G, S, D)は次のように定義される:"正整数k, 無向グラフG=(V, E), 指定点集合S⊆V, 次数増加可能点集合D⊆Vが与えられたときに, (V, E∪E')におけるSの点連結度がk以上であるような最小本数の辺集合E'⊆{(u, v)|u, v∈D}を求めよ."ここで, GにおけるSの点連結度とは, Gから除去するとSの点を含む連結成分数が2以上となるか又はSの点が1点だけとなるような, 点集合の最小点数である.V-Dの点をGの次数増加禁止点と呼ぶ.本稿では, 2VCA(G, S, D)又は3VCA(G, S, D)に対して, 解の存在性判定と解を求めることがそれぞれ, O(|V|+|E|)又はO(|V|(|V|+|E|))時間で実行できることを示す.(
- 社団法人電子情報通信学会の論文
- 2000-01-19
著者
関連論文
- 点次数の増加上限制約を持つ2点連結グラフに対する線形時間3点連結化アルゴリズム
- グラフの付加辺多重度に上限を持つk-辺連結化問題
- 3-連結グラフに対する点被覆及び連結点被覆問題について
- プリント基板レイアウト設計における非平面接続数の極小化手法
- 与えられた制約を満たす矩形双対グラフ描画手法
- 次数制約付きのグラフに対する指定点3辺連結化問題の解法
- 次数制約付きのグラフに対する指定点3辺連結化問題の解法
- 次数制約付きのグラフに対する指定点k辺連結化について
- 次数増加禁止点を持つグラフの指定点3辺連結化問題に対する線形時間アルゴリズム
- 次数増加禁止点を持つグラフの指定点3点連結化問題に対する線形時間アルゴリズム
- 次数増加禁止点を持つグラフの指定点集合に対する2, 3点連結化問題の解法
- 次数増加禁止点を持つグラフに対する点連結度増加問題
- 次数増加禁止点を持つグラフに対する点連結度増加問題
- グラフの指定点集合に対する3点連結化問題の解法
- グラフの指定点3点連結化問題に対する解法
- グラフの局所辺連結度増加問題に対する近似解法
- グラフのk辺連結化問題に対する新しい近似解法
- ペトリネットの最大発火系列問題に対する発見的アルゴリズムFSDB
- ペトリネットインバリアント算出のためのFourier-Motzkin法の改良実装
- A-12-5 時間付ペトリネットによるスケジューリングに対する発見的解法SDS
- A-12-4 指定プレース集合を含むサポートを持つペトリネットインバリアントの算出法
- 次数制約付きのグラフに対する指定点2点連結化問題の解法
- λ-辺連結グラフにおける指定点集合の(λ+1)-辺連結化のための2-近似アルゴリズムFSA+1
- グラフの最小コスト3-点連結化問題に対する近似アルゴリズム
- CONTEC : 辺交差の制御機能を有するグラフ描画システム
- 複数の指定点集合に対する2辺-及び2点-連結化問題の解法
- 指定サイズ矩形内への矩形双対グラフ描画手法
- いくつかのハイパーグラフ問題に対するPrimal-Dual近似アルゴリズムについて
- 通信ネットワークの(σ+1)辺連結化問題に対する効率的分散アルゴリズムDECA-1
- 通信ネットワークの(σ+1)辺連結化問題に対する効率的分散アルゴリズムDECA-1
- 指定点集合のk辺連結化問題に対する解法
- 3層配線問題の制約付きビア数最小化手法
- 辺付加による(σ+1)-辺連結単純グラフ構成のための効率的アルゴリズム
- 辺付加による(σ+1)-辺連結単純グラフ構成のための効率的アルゴリズム
- グラフの多重辺生成を許さない(σ+1)-辺連結化問題
- グラフの多重辺付加を許さないk辺連結化問題
- ペトリネットの発火系列問題に対する発見的解法FSD