A Linear-Time Algorithm for 2-Step Domination in Block Graphs
Received:April 19, 2014  Revised:January 16, 2015
Key Words: 2-step domination   block graph   algorithm   labeling method  
Fund Project:Supported by the National Natural Science Foundation of China (Grant No.11271365) and the Domestic Senior Visiting Scholar Program in Higher Occupation Colleges in Jiangsu Province (Grant No.2014FX075).
Author NameAffiliation
Yancai ZHAO School of Science, Jiangnan University, Jiangsu 214122, P. R. China
Wuxi City College of Vocational Technology, Jiangsu 214153, P. R. China 
Lianying MIAO Department of Mathematics, China University of Mining and Technology, Jiangsu 221116, P. R. China 
Zuhua LIAO School of Science, Jiangnan University, Jiangsu 214122, P. R. China 
Hits: 2792
Download times: 2875
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.
Citation:
DOI:10.3770/j.issn:2095-2651.2015.03.006
View Full Text  View/Add Comment