小直径图的导出匹配覆盖

来源 :运筹学学报 | 被引量 : 0次 | 上传用户：panmandy

【摘要】

：

设G是一个图，而M1，M2，…，Mk是G的k个导出匹配．称{M1，M2，…，Mk}是图G的一个k-导出匹配覆盖，若V（M1）∪V（M2）∪…∪V（Mk）=V（G）．k-导出匹配覆盖问题是指对任一个给定的图G是否存在一个k-导出匹配覆

【作者】

：

董丽原晋江

【机构】

：

信阳师范学院数学与信息科学学院,郑州大学数学系

【出处】

：

运筹学学报

【发表日期】

：

2008年2期

【关键词】

：

运筹学导出匹配导出匹配覆盖 NP-完备多项式可解 Operations research induced matching induced match

【基金项目】

：

Research supported by the National Natural Science Foundation of China （10671183）.

下载到本地 , 更方便阅读

下载此文赞助VIP

声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架

论文部分内容阅读

设G是一个图，而M1，M2，…，Mk是G的k个导出匹配．称{M1，M2，…，Mk}是图G的一个k-导出匹配覆盖，若V（M1）∪V（M2）∪…∪V（Mk）=V（G）．k-导出匹配覆盖问题是指对任一个给定的图G是否存在一个k-导出匹配覆盖．这篇文章证明了：直径为6的图的2-导出匹配覆盖问题和直径为2的图的3-导出匹配覆盖问题是NP-完备的，直径为2的图的2-导出匹配覆盖问题多项式可解．

其他文献

一类二层多目标规划的若干性质

本文对于下层为线性多目标规划的二层规划问题，在约束域非空有界的条件下证明了可行集的弱拟凸性、连通性，为算法设计提供了理论依据．

期刊

运筹学二层规划多目标规划连通性Operations research bilevel programming problem multi-objec

山楂的妙用

炖猪肉:炖猪肉不要用急火,火势一急,肉便紧缩在一起了。如果在炖肉的时候放几个山楂,肉可以很快炖得酥烂。炖鸡:炖老鸡时,可放3～4个山楂,这样鸡肉

期刊

山楂炖牛肉猪肉炖肉炖鸡消化不良山植炖羊肉鸡肉烤熟

与网络犯罪“短兵相接”——青岛市报警处置中心推动网监工作

2003年7月,青岛被确定为报警处置中心试点单位之一,经过精心准备和建设,去年元月6日,青岛市公安局信息网络安全报警处置中心正式开通,开始受理各类网络安全事件报警和计算机

期刊

网络犯罪青岛市报警处置中心报警渠道网监调度指挥

小直径图的导出匹配覆盖

其他学术论文