k-節点・領域連結問題の性質と解法

スポンサーリンク

概要

論文の詳細を見る
グラフの強固さを測る指標として連結度がある。通信網では、複数の交換機が集まって一つの論理的な領域を形成していることがある。交換機をグラフの節点と考えると、節点と領域(節点の部分集合)の連結度が重要となる。本稿では、節点と領域の連結度を意味する、NA連結(node-to-area connection)という概念を導入した。そして与えられたグラフに対し、k-連結性を保持する全域部分グラフは、任意の節点・領域間に対しk-NA連結性も保持することを証明した。この性質を用いれば、k-NA連結性を保持する最小全域部分グラフを求める問題(NP困難)に対し、相対近似誤差が2倍以内の解を線形時間で得ることができる。また、NA連結度による評価と連結度による評価による必要な枝数等を計算機で評価し、互いの数値的差異が小さいことを確かめた。
社団法人電子情報通信学会の論文
1993-11-26

著者

関連論文

もっと見る

スポンサーリンク