Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
13431269 | Information Processing Letters | 2020 | 12 Pages |
Abstract
Two vertices in a graph are said to 2-step dominate each other if they are at distance 2 apart. A set S of vertices in a graph G=(V,E) is a hop dominating set of G if every vertex outside S is 2-step dominated by some vertex of S. Given a graph G, Min-HDS is the problem of finding a hop dominating set of G of minimum cardinality. The decision version of Min-HDS is known to be NP-complete for planar bipartite graphs and planar chordal graphs, and hence for bipartite graphs and chordal graphs. In this paper, we present a linear time algorithm for computing a minimum hop dominating set in bipartite permutation graphs, which is a subclass of bipartite graphs. We also show that Min-HDS cannot be approximated within a factor of (1âε)lnâ¡|V|, unless P=NP and can be approximated within a factor of 1+lnâ¡(Î(Îâ1)+1), where Î denotes the maximum degree in the graph G. Finally, we show that Min-HDS is APX-complete for bipartite graphs of maximum degree 3.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Michael A. Henning, Saikat Pal, D. Pradhan,