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 条

[1]

[Anonymous], J I ENG INDIA

[2]

Awerbuch Baruch., 1990, 31st Annual Symposium on Foundations of Computer Science, 1990, VII, P503

[3] Bounds on the hop domination number of a tree [J].

Ayyaswamy, S. K. ;

Krishnakumari, B. ;

Natarajan, C. ;

Venkatakrishnan, Y. B. .

PROCEEDINGS OF THE INDIAN ACADEMY OF SCIENCES-MATHEMATICAL SCIENCES, 2015, 125 (04) :449-455

[4] The k-neighbourhood-covering problem on interval graphs [J].

Barman, Sambhu Charan ;

Pal, Madhumangal ;

Mondal, Sukumar .

INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS, 2010, 87 (09) :1918-1935

[5] An efficient algorithm to find next-to-shortest path on permutation graphs [J].

Barman S.C. ;

Mondal S. ;

Pal M. .

Journal of Applied Mathematics and Computing, 2009, 31 (1-2) :369-384

[6]

Basuchowdhuri P, 2014, LECT NOTES COMPUT SC, V8321, P137, DOI 10.1007/978-3-319-04126-1_12

[7] GenBank [J].

Benson, DA ;

Boguski, MS ;

Lipman, DJ ;

Ostell, J ;

Ouellette, BFF ;

Rapp, BA ;

Wheeler, DL .

NUCLEIC ACIDS RESEARCH, 1999, 27 (01) :12-17

[8]

Bera D., 2001, KOREAN J COMPUTATION, V8, P295

[9]

Berchtold S., 1998, SIGMOD Record, V27, P142, DOI 10.1145/276305.276318

[10]

Berchtold S, 1996, PROCEEDINGS OF THE INTERNATIONAL CONFERENCE ON VERY LARGE DATA BASES, P28

← 1 2 3 4 5 6 7 8 9 →