| 赵衍才,苗连英,廖祖华.块图的2-步长控制问题的一个线性时间算法[J].数学研究及应用,2015,35(3):285~290 |
| 块图的2-步长控制问题的一个线性时间算法 |
| A Linear-Time Algorithm for 2-Step Domination in Block Graphs |
| 投稿时间：2014-04-19 修订日期：2015-01-16 |
| DOI：10.3770/j.issn:2095-2651.2015.03.006 |
| 中文关键词: 2-步长控制 块图 算法 标号方法 |
| 英文关键词:2-step domination block graph algorithm labeling method |
| 基金项目:国家自然科学基金(Grant No.11271365), 江苏省高等职业院校国内高级访问学者计划资助项目(Grant No.2014FX075). |
|
| 摘要点击次数: 2935 |
| 全文下载次数: 2987 |
| 中文摘要: |
| 图的2-步长控制问题是指找到图的一个最小基数的点子集$D$,使得该图的任意一个顶点或者在$D$中,或者到$D$中一点的距离恰好为2.通过标号方法的运用,本文给出了解决块图的2-步长控制问题的一个线性时间算法. |
| 英文摘要: |
| 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. |
| 查看全文 查看/发表评论 下载PDF阅读器 |
