| 一个求外平面图最小反馈点集的多项式时间算法 |
| |
| 引用本文： | 陈勇,张少强.一个求外平面图最小反馈点集的多项式时间算法[J].济南大学学报(自然科学版),2004,18(1):1-5. |
| |
| 作者姓名： | 陈勇 张少强 |
| |
| 作者单位： | 1. 济南大学,理学院,山东,济南,250022;山东大学,数学院,山东,济南,250100
2. 山东大学,数学院,山东,济南,250100;天津师范大学,数学系,天津,300017 |
| |
| 基金项目： | 国家自然科学基金资助项目 (10 2 710 65 ) |
| |
| 摘 要： | 如果从一个图中去掉某些顶点后得到的导出子图是无圈图，则所去的那些顶点组成的集合就是原图的反馈点集。本文讨论外平面图的反馈点集并给出了一个求外平面图最小反馈点集的多项式时间算法。
|
| 关 键 词： | 外平面图 反馈点集 多项式时间算法 |
| 文章编号： | 1671-3559(2004)01-0001-05 |
| 修稿时间： | 2003年6月10日 |
A Polynomial Algorithm for Minimum-Cardinality Feedback Vertex Set Problem in Outerplanar Graphs |
| |
| CHEN Yong ,ZHANG Shao-qiang.A Polynomial Algorithm for Minimum-Cardinality Feedback Vertex Set Problem in Outerplanar Graphs[J].Journal of Jinan University(Science & Technology),2004,18(1):1-5. |
| |
| Authors: | CHEN Yong ZHANG Shao-qiang |
| |
| Institution: | CHEN Yong 1,2,ZHANG Shao-qiang 2,3 |
| |
| 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. |
| |
| Keywords: | outerplanar graphs feedback vertex set polynomial algorithm |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
|
