| 直线簇上区间图的最小全控制集和最小配对控制集 |
| |
| 引用本文： | 皮军德,林浩.直线簇上区间图的最小全控制集和最小配对控制集[J].河南科学,2007,25(4):537-541. |
| |
| 作者姓名： | 皮军德 林浩 |
| |
| 作者单位： | 河南工业大学,理学院,郑州,450052;河南工业大学,理学院,郑州,450052 |
| |
| 基金项目： | 国家自然科学基金
,
河南工业大学校科研和校改项目 |
| |
| 摘 要： | 研究了广义区间图的最小全控制集和最小配对控制集的计算问题.对有一个公共交点的直线簇上的区间图,给出了计算其最小全控制集的O(n)时间算法和其最小配对控制集的O(n+m)时间算法.
|
| 关 键 词： | 区间图 全控制集 配对控制集 算法 |
| 文章编号： | 1004-3918（2007）04-537-05 |
| 修稿时间： | 2007-04-08 |
Minimum Total Dominating Sets and Paired Dominating Sets of Intervals on Lines |
| |
| PI Jun-de,LIN Hao.Minimum Total Dominating Sets and Paired Dominating Sets of Intervals on Lines[J].Henan Science,2007,25(4):537-541. |
| |
| Authors: | PI Jun-de LIN Hao |
| |
| Institution: | College of Science, Henan University of Technology, Zhengzhou 450052, China |
| |
| Abstract: | In this paper,we study the problem of computing minimum total dominating sets and minimum paired dominating sets of generalized interval graphs.For the interval graph G=(V,E) with n intervals on lines which intersect at a single point,we propose an O(n)-time algorithm for computing the minimum total dominating sets and an O(n m)-time algorithm for computing the minimum paired dominating sets. |
| |
| Keywords: | interval graphs total dominating set paired dominating set algorithms |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
|
