Geodesic
An optimal algorithm for computing minimum \(k\)-hop dominating set of permutation graphs
Serdica Mathematical Journal, Tome 46 (2020) no. 1, pp. 43-60

Voir la notice de l'article provenant de la source Bulgarian Digital Mathematics Library

A  \(k\)-hop dominating set (\(k\)-HDS) \(D\) of a graph \(G = (V,E)\) is a subset of \(V\) such that every vertex \(x\in V\) is within \(k\)-steps from at least one vertex \(y\in D\), i.e., \(d(x,y)\leq k\), where \(k\) is a fixed positive integer. A \(k\)-hop dominating set \(D\) is said to be minimal if there does not exist any \(H\subset D\) such that \(H\) is a \(k\)-HDS of \(G\). If a dominating set \(D\) is minimal as well as it is \(k\)-HDS then it is said to be minimum \(k\)-hop dominating set. In this paper, we present an optimal algorithm to compute a minimum \(k\)-HDS of permutation graphs with \(n\) vertices which runs in \(O(n)\) time.
Keywords: Design and analysis of algorithms, \(k\)-hop domination, permutation graphs, 05C30, 05C12, 68R10, 68Q25 
@article{SMJ2_2020_46_1_a3,
     author = {Barman, Sambhu and Pal, Madhumangal and Mondal, Sukumar},
     title = {An optimal algorithm for computing minimum \(k\)-hop dominating set of permutation graphs},
     journal = {Serdica Mathematical Journal},
     pages = {43--60},
     publisher = {mathdoc},
     volume = {46},
     number = {1},
     year = {2020},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/SMJ2_2020_46_1_a3/}
}
TY  - JOUR
AU  - Barman, Sambhu
AU  - Pal, Madhumangal
AU  - Mondal, Sukumar
TI  - An optimal algorithm for computing minimum \(k\)-hop dominating set of permutation graphs
JO  - Serdica Mathematical Journal
PY  - 2020
SP  - 43
EP  - 60
VL  - 46
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/SMJ2_2020_46_1_a3/
LA  - en
ID  - SMJ2_2020_46_1_a3
ER  - 
%0 Journal Article
%A Barman, Sambhu
%A Pal, Madhumangal
%A Mondal, Sukumar
%T An optimal algorithm for computing minimum \(k\)-hop dominating set of permutation graphs
%J Serdica Mathematical Journal
%D 2020
%P 43-60
%V 46
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/SMJ2_2020_46_1_a3/
%G en
%F SMJ2_2020_46_1_a3
Barman, Sambhu; Pal, Madhumangal; Mondal, Sukumar. An optimal algorithm for computing minimum \(k\)-hop dominating set of permutation graphs. Serdica Mathematical Journal, Tome 46 (2020) no. 1, pp. 43-60. http://geodesic.mathdoc.fr/item/SMJ2_2020_46_1_a3/