3-連結グラフに対する点被覆及び連結点被覆問題について
スポンサーリンク
概要
- 論文の詳細を見る
本論文では,3-連結グラフに対する点被覆及び連結点被覆問題について考える.但し,3-連結グラフの部分族である準車輪の族及び車輪拡大グラフの族に対象を制限して問題を考える.本稿では,まず車輪拡大グラフに対する点被覆問題がNP完全問題であることを示す.これと既存の結果とを合わせれば,車輪拡大グラフに対する連結点被覆問題もまたNP完全問題であることが示される.次に,準車輪グラフに対する連結点被覆問題を線形マトロイドマッチング問題に帰着させ,線形マトロイドマッチング問題の解法を利用することにより,準車輪グラフに対する最小連結点被覆がO(|V|^3)で定められることを示す.
- 1995-11-17
著者
-
渡邊 敏正
広島大学工学部第二類回路システム工学講座
-
柴田 勲男
広島大学工学部第二類(電気系)回路システム工学講座
-
藤戸 敏弘
広島大学工学部第二類(電気系)回路システム工学講座
-
藤戸 敏弘
広島大学工学部 第二類 回路・システム工学講座
関連論文
- グラフの付加辺多重度に上限を持つk-辺連結化問題
- 3-連結グラフに対する点被覆及び連結点被覆問題について
- 枝重み付きカクタスに対する発火系列問題の解法
- プリント基板レイアウト設計における非平面接続数の極小化手法
- 与えられた制約を満たす矩形双対グラフ描画手法
- 次数増加禁止点を持つグラフの指定点集合に対する2, 3点連結化問題の解法
- グラフの指定点3点連結化問題に対する解法
- ペトリネットの最大発火系列問題に対する発見的アルゴリズムFSDB
- ペトリネットインバリアント算出のためのFourier-Motzkin法の改良実装
- A-12-5 時間付ペトリネットによるスケジューリングに対する発見的解法SDS
- A-12-4 指定プレース集合を含むサポートを持つペトリネットインバリアントの算出法
- CONTEC : 辺交差の制御機能を有するグラフ描画システム
- 劣モジュラ被覆問題の近似について
- 複数の指定点集合に対する2辺-及び2点-連結化問題の解法
- 指定サイズ矩形内への矩形双対グラフ描画手法
- いくつかのハイパーグラフ問題に対するPrimal-Dual近似アルゴリズムについて
- 通信ネットワークの(σ+1)辺連結化問題に対する効率的分散アルゴリズムDECA-1
- 通信ネットワークの(σ+1)辺連結化問題に対する効率的分散アルゴリズムDECA-1
- マトロイド的特性に関する点除去問題のプライマル・デュアル法による近似
- 指定点集合のk辺連結化問題に対する解法
- 3層配線問題の制約付きビア数最小化手法
- 辺付加による(σ+1)-辺連結単純グラフ構成のための効率的アルゴリズム
- 辺付加による(σ+1)-辺連結単純グラフ構成のための効率的アルゴリズム
- グラフの多重辺生成を許さない(σ+1)-辺連結化問題
- グラフの多重辺付加を許さないk辺連結化問題
- ペトリネットの発火系列問題に対する発見的解法FSD