东篱科研大数据发现系统（DRDS）

位置：成果数据库 > 期刊 > 期刊详情页

直径为5的图的2-导出匹配划分和2-导出匹配覆盖问题的NP-完全性

ISSN号：1007-6093
期刊名称：《运筹学学报》
时间：0
分类：O157.5[理学—数学;理学—基础数学] O153.1[理学—数学;理学—基础数学]
作者机构：[1]曲阜师范大学计算机科学学院,日照276826, [2]山东大学数学与系统科学学院,济南250100
相关基金：The work is supported by NNSF （10471078） of China and R.FDP （20040422004） of Higher Education, Promotional Foundation （2005BS01016） for Excellent Middle-aged or Young Scientists of Shandong Province, UF（XJ0609） and DRF of QFNU.

关键词：运筹学, 导出匹配, 导出匹配划分, 导出匹配覆盖, NP-完全, Operations research, induced matching, induced matching partition, induced matching cover, NP-complete

中文摘要：

给定一个简单图G和正整数k，具有完美匹配的图G的k-导出匹配划分是对顶点集V（G）的一个k-划分（V1，V2,…，Vk），其中对每一个i（1≤i≤k），由Vi导出的G的子图G[Vi]是1-正则的．k-导出匹配划分问题是指对给定的图G，判定G是否存在一个k-导出匹配划分．令M1，M2…，Mk为图G的k个导出匹配，如果V（M1）U（M2）U…UV（Mk）=V（G），则我们称{M1，M2…．，Mk）是G的k-导出匹配覆盖．k-导出匹配覆盖问题是指对给定的图G，判定G是否存在k-导出匹配覆盖．本文给出了Yang，Yuan和Dong所提出问题的解，证明了直径为5的图的导出匹配2-划分问题和导出匹配2-覆盖问题都是NP-完全的．

英文摘要：

Given a simple graph G and a positive integer k, a k-induced-matching partition of a graph G having a perfect matching is a k-partition （V1, V2,……, Vk） of V （G） such that for each i （1 ≤ i ≤ k）, the subgraph G [Vi] of G induced by Vi is 1-regular. The k-induced-matching partition problem asks whether a given graph G has a k-inducedmatching partition or not. Let M1,M2,... Mk be k induced matching of G. We say {M1, M2,..., Mk} is a k-induced-matching cover of G if V（M1） U V（M2） U... U V（Mk） = V（G）. The k-induced-matching cover problem asks whether a given graph G has a k- induced-matching cover or not. In this paper, 2-induced-matching partition problem and 2-induced-matching cover problem of graphs with diameter 5 are proved to be NP- complete, which gives a solution of Yang Yuan and Dong.

同期刊论文项目