次数増加禁止点を持つグラフに対する点連結度増加問題

概要

論文の詳細を見る
次数増加禁止点を持つグラフの指定点集合に対するk点連結化問題kVCA (G, S, D)は次のように定義される:正整数k,無向グラフG = (V, E),指定点集合S ⫃ V,次数増加可能点集合D ⫃ Vが与えられたときに,(V, E⋃E^1)におけるSの点連結度がk以上であるような最小本数の辺集合E^1 ⫃ {(u, v)∣u, v ∈ D}を求めよ.ここで,GにおけるSの点連結度とは,Gから除去するとSの点を含む連結成分数が2以上となるか又はSの点が1点だけとなるような点集合の最小点数である.V - Dの点をGの次数増加禁止点と呼ぶ.kVCA (G, S, D), kVCA (G, V, D), kVCA (G, V, V), kVCA (G, S, S)をそれぞれk-SD, k-VD, k-VV, k-SSと表す.本稿では,まず(1) k-SDに解が存在するための必要十分条件を与える.次に(2) k-VDに対する解の存在性判定と解を求めることがk-VVの解法を用いることにより可能であること,及び(3) k <__- 3のときのk-SSがk-VDへの帰着により線形時間で解けることを示す.
社団法人電子情報通信学会の論文
1999-12-10