一种移除所有皇冠的扩展NT算法

计算机科学 ›› 2007, Vol. 34 ›› Issue (10): 173-176.

• 软件工程与数据库技术 • 上一篇下一篇

一种移除所有皇冠的扩展NT算法

常乐王建新陈建二

中南大学信息科学与工程学院,长沙410083

出版日期:2018-11-16 发布日期:2018-11-16
基金资助:
国家自然科学基金重点项目：生物信息学中的相关组合理论和算法研究（60433020）.

CHANG Le WANG, Jian-Xin, CHEN Jian-Er （School of Information Science and Engineering, Central South University, Changsha 410083）

Online:2018-11-16 Published:2018-11-16

摘要/Abstract

摘要： 皇冠分解和NT算法长久以来被认V1为是在参数化点覆盖的求核问题中有着广泛应用的两种相互独立的方法。NT算法将给定的图分成V2，V1和V1／2三部分，将砜和V1移除从而完成图的分解。而皇冠分解则是找到尽可能多的皇冠结构，删除这些皇冠以降低图规模。最近的研究结果表明NT算法和皇冠分解存在很强的内在联系：NT算法中的砜，V1部分正好构成一个皇冠结构。本文进一步研究了皇冠分解和NT算法的内在联系，提出了严格皇冠和非严格皇冠的概念，提出了一般图中存在皇冠的判定定理，证明了NT算法可以移除一般图中存在的所有严格皇冠。

关键词: 点覆盖参数计算核心化算法皇冠分解 NT算法

Abstract: Crown reduction and NT algorithm had been thought tion of the parameterized Vertex Cover problem. NT algorithm to be two different approaches of great use in kernelizadivides a given graph into three parts called V0 ,V1 and V1/z removes V0 and V1 from the

Key words: Vertex cover, Parameterized computation, Kernelization algorithms, Crown reduction, NT algorithm

常乐王建新陈建二. 一种移除所有皇冠的扩展NT算法[J]. 计算机科学, 2007, 34(10): 173-176. https://doi.org/

CHANG Le WANG, Jian-Xin, CHEN Jian-Er （School of Information Science and Engineering, Central South University, Changsha 410083）. [J]. Computer Science, 2007, 34(10): 173-176. https://doi.org/

参考文献

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed

一种移除所有皇冠的扩展NT算法

PDF (PC)

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 0

Metrics

本文评价

推荐阅读 0