赵衍才,苗连英,廖祖华.块图的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).
作者单位
赵衍才 江南大学理学院, 江苏 无锡 214122; 中国矿业大学数学系, 江苏 徐州 221116 
苗连英 无锡城市职业技术学院江苏 无锡 214153 
廖祖华 江南大学理学院, 江苏 无锡 214122 
摘要点击次数: 1085
全文下载次数: 1164
中文摘要:
      图的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阅读器