三种新变形的全一问题

• 作者: 张晓岩 李学良
• 来源期刊: 数学物理学报
• 学科: 数学
• 关键词: 全一问题 最小权的完美匹配 图算法
• 年，卷（期）: 2008,（4）
• 页码范围: 619-626
• 页数: 8页
• 分类号: O157.5
• 字数: 8145字
• 语种: 中文

摘要

该文研究三种新变形的全一问题及最小全一问题.原始的全一问题可被形象的称为顶点点亮顶点问题,而这三类新问题则分别被称为顶点点亮边问题,边点亮顶点问题,边点亮边问题.顶点点亮顶点问题已经得到了广泛的研究.比如,解的存在性问题和求解的有效算法已经被解决,一般图上的最小顶点点亮顶点问题已经被证明是NP-完备的,树、单圈图和双圈图上的最小顶点点亮顶点问题的线性时间最优算法也已被给出等.该文对于顶点点亮边问题,证明一个图有解当且仅当它是二部图,因此只可能有两组解和最优解.对于边点亮顶点问题,证明一个图有解当且仅当它包含偶数个顶点,并通过将其最优问题多项式变换成最小权的完美匹配问题,得出一般图上的最小边点亮顶点问题可在多项式时间内求解.边点亮边问题可归约成线图上的顶点点亮顶点问题.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	张晓岩	南京师范大学数学与计算机科学学院	7	30	2.0	5.0
2	李学良	南开大学组合数学中心	19	89	5.0	9.0