|
|||||
|
|
| 一个求外平面图最小顶点赋权反馈点集的线性时间算法 | |
| 引用本文： | 张少强,王骁力,李国君.一个求外平面图最小顶点赋权反馈点集的线性时间算法[J].数学研究及应用,2004,24(4):610-618. |
| 作者姓名： | 张少强 王骁力 李国君 |
| 作者单位： | 1. 天津师范大学计算机与信息工程学院,天津,300074 2. 天津师范大学计算机与信息工程学院,天津,300074;南阳师范学院数学系,河南,南阳,473061 3. 天津师范大学计算机与信息工程学院,天津,300074;中国科学院软件研究所,北京,100080 |
| 基金项目： | SupportedbyNationalNaturalScienceFoundofChina(60373025) |
| 摘 要： | 若从一个图中去掉某些顶点后得到的导出子图是无圈图,则所去的那些顶点组成的集合就是原图的反馈点集.本文主要考虑外平面图中的反馈点集并给出了一个求外平面图最小顶点赋权反馈点集的线性时间算法. |
| 关 键 词： | 外平面图 反馈点集 线性时间算法 |
| 收稿时间： | 2002/11/26 0:00:00 |
A Linear Time Algorithm for Minimum-Weight Feedback Vertex Set Problem in Outerplanar Graphs |
|
| ZHANG Shao-qiang,WANG Xiao-li and LI Guo-jun.A Linear Time Algorithm for Minimum-Weight Feedback Vertex Set Problem in Outerplanar Graphs[J].Journal of Mathematical Research with Applications,2004,24(4):610-618. | |
| Authors: | ZHANG Shao-qiang WANG Xiao-li and LI Guo-jun |
| Institution: | School of Comp. & Info. Engineering. Tianjin Normal University; Tianjin; China;School of Mathematics and Systems Science; Shandong University; Jinan; China; Dept. of Math.; Nanyang Normal University; Henan; China;School of Mathematics and Systems Science; Shandong University; Jinan; China; Inst. of Software; Chinese Academy of Sciences; Beijing, China |
| Abstract: | 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. |
| Keywords: | outerplanar graphs feedback vertex set linear time algorithm |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ | |
| 点击此处可从《数学研究及应用》浏览原始摘要信息 | |
| 点击此处可从《数学研究及应用》下载免费的PDF全文 | |