| 块图的2-步长控制问题的一个线性时间算法 |
| |
| 引用本文： | 赵衍才,苗连英,廖祖华. 块图的2-步长控制问题的一个线性时间算法[J]. 数学研究及应用, 2015, 35(3): 285-290 |
| |
| 作者姓名： | 赵衍才 苗连英 廖祖华 |
| |
| 作者单位： | 江南大学理学院, 江苏 无锡 214122; 中国矿业大学数学系, 江苏 徐州 221116;无锡城市职业技术学院，江苏 无锡 214153;江南大学理学院, 江苏 无锡 214122 |
| |
| 基金项目： | 国家自然科学基金(Grant No.11271365), 江苏省高等职业院校国内高级访问学者计划资助项目(Grant No.2014FX075). |
| |
| 摘 要： | The 2-step domination problem is to find a minimum vertex set D of a graph such that every vertex of the graph is either in D or at distance two from some vertex of D.In the present paper,by using a labeling method,we provide an O(m) time algorithm to solve the2-step domination problem on block graphs,a superclass of trees.
|
| 关 键 词： | 2-step domination block graph algorithm labeling method |
| 收稿时间： | 2014-04-19 |
| 修稿时间： | 2015-01-16 |
A Linear-Time Algorithm for 2-Step Domination in Block Graphs |
| |
| Yancai ZHAO,Lianying MIAO and Zuhua LIAO. A Linear-Time Algorithm for 2-Step Domination in Block Graphs[J]. Journal of Mathematical Research with Applications, 2015, 35(3): 285-290 |
| |
| Authors: | Yancai ZHAO Lianying MIAO Zuhua LIAO |
| |
| Affiliation: | School of Science, Jiangnan University, Jiangsu 214122, P. R. China; Wuxi City College of Vocational Technology, Jiangsu 214153, P. R. China;Department of Mathematics, China University of Mining and Technology, Jiangsu 221116, P. R. China;School of Science, Jiangnan University, Jiangsu 214122, P. R. China |
| |
| Abstract: | The 2-step domination problem is to find a minimum vertex set $D$ of a graph such that every vertex of the graph is either in $D$ or at distance two from some vertex of $D$. In the present paper, by using a labeling method, we provide an $O(m)$ time algorithm to solve the 2-step domination problem on block graphs, a superclass of trees. |
| |
| Keywords: | 2-step domination block graph algorithm labeling method |
| 本文献已被 CNKI 等数据库收录！ |
| 点击此处可从《数学研究及应用》浏览原始摘要信息 |
|
点击此处可从《数学研究及应用》下载全文 |
|
