一个求外平面图最小顶点赋权反馈点集的线性时间算法

作者：张少强; 王骁力; 李国君

来源：数学研究与评论, 2004, 24(4): 610-618.

DOI：10.3770/j.issn.2095-2651.2004.04.006

• 外平面图
• 反馈点集
• 线性时间算法

若从一个图中去掉某些顶点后得到的导出子图是无圈图,则所去的那些顶点组成的集合就是原图的反馈点集.本文主要考虑外平面图中的反馈点集并给出了一个求外平面图最小顶点赋权反馈点集的线性时间算法.

• 出版日期2004
• 单位南阳师范学院; 天津师范大学; 中国科学院软件研究所