寻找2-边连通子图的一种近似算法

作者：刘芝梅; 曹炬; 刘毅

来源：应用数学, 2007, 20(S1): 23-26.

• 2-边连通
• 生成子图
• 去边
• 连通分支

本文对问题"找出一个给定无向图的最小(即边数最少)2-边连通生成子图"给出了一个新的可行近似算法.该算法采用去边思想,并不借助于生成树,而是先把原图拆散,然后加点、删边得到一个2-边连通的生成子图.

• 单位
  华中科技大学