| 张少强,王骁力,李国君.一个求外平面图最小顶点赋权反馈点集的线性时间算法(英文)[J].数学研究及应用,2004,24(4):610~618 |
| 一个求外平面图最小顶点赋权反馈点集的线性时间算法(英文) |
| A Linear Time Algorithm for Minimum-Weight Feedback Vertex Set Problem in Outerplanar Graphs |
| 投稿时间：2002-11-26 |
| DOI：10.3770/j.issn:1000-341X.2004.04.006 |
| 中文关键词: 外平面图 反馈点集 线性时间算法 |
| 英文关键词:outerplanar graphs feedback vertex set linear time algorithm. |
| 基金项目: |
| 作者 | 单位 | | 张少强 | 天津师范大学计算机与信息工程学院,天津,300074 | | 王骁力 | 天津师范大学计算机与信息工程学院,天津,300074
南阳师范学院数学系,河南,南阳,473061 | | 李国君 | 天津师范大学计算机与信息工程学院,天津,300074
中国科学院软件研究所,北京,100080 |
|
| 摘要点击次数: 2581 |
| 全文下载次数: 1143 |
| 中文摘要: |
| 若从一个图中去掉某些顶点后得到的导出子图是无圈图,则所去的那些顶点组成的集合就是原图的反馈点集.本文主要考虑外平面图中的反馈点集并给出了一个求外平面图最小顶点赋权反馈点集的线性时间算法. |
| 英文摘要: |
| A subset of the vertex set of a graph is a feedback vertex set of the graph ifthe resulting graph is a forest after removing the vertex subset from the graph.In thispaper, we study the minimum-weight feedback vertex set problem in outerplanar graphs and present a linear time algorithm to solve it. |
| 查看全文 查看/发表评论 下载PDF阅读器 |
|
|
|
