An optimal algorithm to find minimum k-hop dominating set of interval graphs

被引：10
作者：
Barman, Sambhu Charan [1 ]
Pal, Madhumangal [2 ]
Mondal, Sukumar [3 ]
机构：
[1] Shahid Matangini Hazra Govt Coll Women, Dept Math, Tamluk 721649, Purba Medinipur, India
[2] Vidyasagar Univ, Dept Appl Math, Oceanol & Comp Programming, Midnapore 721102, India
[3] Raja NL Khan Womens Coll, Dept Math, Midnapore 721102, India
来源：
DISCRETE MATHEMATICS ALGORITHMS AND APPLICATIONS | 2019年 / 11卷 / 02期
关键词：
Design of algorithms; analysis of algorithms; k-hop domination; interval graphs; OPTIMAL PARALLEL ALGORITHM; PAIRED-DOMINATION; COVERING PROBLEM; TUPLE DOMINATION; TIME ALGORITHM; TREES;
D O I：
10.1142/S1793830919500162
中图分类号：
O29 [应用数学];
学科分类号：
070104 ;
摘要：
For a fixed positive integer k, a k-hop dominating set D of a graph G = (V, E) is a subset of V such that every vertex x is an element of V is within k-steps from at least one vertex y is an element of D, i. e., d(x, y) <= k. A k-hop dominating set D is said to be minimal if there does not exist any D' subset of D such that D' is a k-hop dominating set of G. A dominating set D is said to be minimum k-hop dominating set, if it is minimal as well as it is k-hop dominating set. In this paper, we present an optimal algorithm to find a minimum k-hop dominating set of interval graphs with n vertices which runs in O(n) time.
引用
收藏
页数：18
相关论文
共 83 条
[11]  
Berger E., 1999, TECHNICAL REPORT
[12]  
Bertossi A.A., 1988, SIAM J DISCRETE MATH, V1, P317
[13]   TESTING FOR CONSECUTIVE ONES PROPERTY, INTERVAL GRAPHS, AND GRAPH PLANARITY USING PQ-TREE ALGORITHMS [J].
BOOTH, KS ;
LUEKER, GS .
JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1976, 13 (03) :335-379
[14]  
CARLISLE MC, 1991, LECT NOTES COMPUT SC, V497, P90
[15]  
Chang G. J., 2013, HDB COMBINATORIAL OP, P339
[16]   The weighted independent domination problem is NP-complete for chordal graphs [J].
Chang, GJ .
DISCRETE APPLIED MATHEMATICS, 2004, 143 (1-3) :351-352
[17]   Weighted domination of cocomparability graphs [J].
Chang, MS .
DISCRETE APPLIED MATHEMATICS, 1997, 80 (2-3) :135-148
[18]   An optimal algorithm for finding the minimum cardinality dominating set on permutation graphs [J].
Chao, HS ;
Hsu, FR ;
Lee, RCT .
DISCRETE APPLIED MATHEMATICS, 2000, 102 (03) :159-173
[19]   BREADTH-1ST TRAVERSAL OF TREES AND INTEGER SORTING IN PARALLEL [J].
CHEN, CCY ;
DAS, SK .
INFORMATION PROCESSING LETTERS, 1992, 41 (01) :39-49
[20]   A linear-time algorithm for paired-domination problem in strongly chordal graphs [J].
Chen, Lei ;
Lu, Changhong ;
Zeng, Zhenbing .
INFORMATION PROCESSING LETTERS, 2009, 110 (01) :20-23
123456789