- 著者
-
田岡 智志
渡邊 敏正
- 出版者
- 一般社団法人電子情報通信学会
- 雑誌
- 電子情報通信学会技術研究報告. COMP, コンピュテーション (ISSN:09135685)
- 巻号頁・発行日
- vol.99, no.549, pp.73-80, 2000-01-19
- 参考文献数
- 24
k辺連結化問題とは、与えられた無向グラフG=(V, E)に付加して得られるグラフG'=(V, E∪E')がk辺連結となるような最小辺集合E'を求める問題である。本稿では、"辺付加により新たに多重辺を作らない"、という条件を加えたk辺連結化問題を扱う。一般には、この問題はNP-hardであり、Gの葉と呼ばれる点集合の総数により問題の難しさが変わることが知られている。本稿では、Gの辺連結度をσとするとき、k=σ+1且つGが2σ+6個未満の葉を持つ場合を考え、リーフグラフの最大マッチングにより生成される葉数と不飽和葉数の関係により、多項式時間の最適解法、あるいは、近似比3 / 2の近似解法、それぞれを提案する。