在森林和单圈图上的0-1最大独立集问题的逆问题

代理获取

页面导航

目录
摘要
著录项
相似文献
相关主题

摘要

一个组合优化问题的逆问题，是给出一个组合优化问题的实例和一个可行解，这个目标是尽可能少的修改给定的数据使得在修改后的数据中这个给定的可行解成为这个给定实例的最优解。一个逆问题我们能把它看做是从一个解出发推理出来的参量。一般来说，对于很多问题，我们都能证明他的逆问题比他的原始问题困难度更大，对于很多多项式时间可解的问题，他的逆问题都是NP-hard的。对于最大独立集问题（MIS)是一类NP-hard问题。它的逆问题被定义为（IMIS)。在特殊情况下，如果这个问题中的权重被限制为{0，1}，这时候，这个问题被叫做0-1最大独立集问题的逆问题，我们用IMIS0.1来定义这个问题。如此，这个问题可以通过改变图形的结构来代替改变它的权重。
　　在本文中，我们在给定的图G中，令 S是它的独立集，0-1最大独立集问题的逆问题（IMIS0.1）是去删除尽可能少的点从而使得S成为 G的最大独立集。我们知道在一般图中（IMIS0.1)是NP-hard。在本文中，针对森林和单圈图这两类图，我们给出了0-1最大独立集问题的逆问题的线性时间的算法。

著录项

作者
刘帅甫;
展开▼
作者单位

新疆大学;

展开▼
授予单位新疆大学;
学科数学
授予学位硕士
导师姓名张昭;
年度 2016
页码
总页数
原文格式 PDF
正文语种中文
中图分类图论;
关键词
组合优化; 最大独立集; 单圈图; 逆问题; 线性时间; 近似算法;

相似文献

中文文献
外文文献
专利

1. 多连通域上的双解析函数Riemann边值逆问题 [J] . 史西专 ,赵秀兰 . 河南教育学院学报（自然科学版） . 2014,第002期
2. 单位圆周上的周期Hilbert边值逆问题的研究 [J] . 赵爽 ,张姮妤 ,丁慧 . 绥化学院学报 . 2013,第011期
3. 双解析函数在开口弧段上的Riemann边值逆问题 [J] . 鄢盛勇 . 云南民族大学学报（自然科学版） . 2012,第002期
4. 开口弧段上的Riemann边值逆问题 [J] . 鄢盛勇 . 云南民族大学学报（自然科学版） . 2011,第002期
5. 广义H空间上的转化定理的应用及其逆问题 [J] . 门少平 . 工程数学学报 . 2000,第003期
6. 开口弧段上的Ｒｉｅｍａｎｎ跳跃逆问题 [C] . 李星 . 第三届全国计算力学会议 . 1992
7. 保域上对称矩阵群逆问题 [A] . 井世丽 . 2007

在森林和单圈图上的0-1最大独立集问题的逆问题

目录

摘要

著录项

相似文献

相关主题

期刊订阅