节点文献

一个求外平面图最小反馈点集的多项式时间算法

A Polynomial Algorithm for Minimum-Cardinality Feedback Vertex Set Problem in Outerplanar Graphs

推荐 CAJ下载
PDF下载
不支持迅雷等下载工具，请取消加速工具后下载。

【Author】 CHEN Yong 1,2 ,ZHANG Shao-qiang 2,3 (1. School of Science,Jinan University,Jinan 250022,China; 2. School of Mathematics and Systems Science,Shandong University, Jinan 250100,China; 3. Math. Dept.,Tianjin Normal University,Tianjin 300017,China)

【机构】济南大学理学院；山东大学数学院山东济南250022；山东大学数学院；山东济南250100；山东济南250100；天津师范大学数学系；天津300017；

【摘要】如果从一个图中去掉某些顶点后得到的导出子图是无圈图 ,则所去的那些顶点组成的集合就是原图的反馈点集。本文讨论外平面图的反馈点集并给出了一个求外平面图最小反馈点集的多项式时间算法。更多还原

【Abstract】 A subset of the vertex set of a graph is a feedback vertex set of the graph if the resulting graph is acyclic after removing the vertex subset from the graph. In this paper,we study the undirected minimum-cardinality feedback vertex set problem in outerplanar graphs and present a polynomial time algorithm to solve it.更多还原

【关键词】外平面图；反馈点集；多项式时间算法；
【Key words】 outerplanar graphs； feedback vertex set； polynomial algorithm；

【基金】国家自然科学基金资助项目 (10 2 710 65 )

【文献出处】济南大学学报(自然科学版) ,Journal of Shandong Institute of Building Materials , 编辑部邮箱 ,2004年01期

【分类号】O157.5
【下载频次】26

知网节下载

节点文献中：

本文链接的文献网络图示:

本文的引文网络

节点文献