控制集与部分控制集问题的原始-对偶算法

摘要：

图的控制集问题是一类应用广泛的组合最优化问题。本文利用控制集和部分控制集问题的整数规划模型和原始-对偶方法,分别给出这两个问题近似度为△+1的近似算法(△为图中顶点最大度).

关键词： 控制集 部分控制集 原始对偶算法 近似算法 图论

作者: 丁玲玲 方奇志

作者单位: 中国海洋大学数学科学学院,山东,青岛,266071

会议类型: 国内会议

会议名称: 2008年全国理论计算机科学学术年会

会议地点: 西安

会议语种:中文

页码: 102-104

在线出版日期: 2008-09-19（万方平台首次上网日期，不代表论文的发表时间）