
doi: 10.7151/dmgt.2403
Summary: In a graph \(G\), a vertex is said to 2-step dominate itself and all the vertices which are at distance 2 from it in \(G\). A set \(D\) of vertices in \(G\) is called a hop dominating set of \(G\) if every vertex outside \(D\) is 2-step dominated by some vertex of \(D\). Given a graph \(G\) and a positive integer \(k\), the hop domination problem is to decide whether \(G\) has a hop dominating set of cardinality at most \(k\). The hop domination problem is known to be NP-complete for bipartite graphs. In this paper, we design a linear time algorithm for computing a minimum hop dominating set in chordal bipartite graphs.
Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.), Graph algorithms (graph-theoretic aspects), chordal bipartite graphs, QA1-939, polynomial time algorithm, hop domination, Mathematics, domination
Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.), Graph algorithms (graph-theoretic aspects), chordal bipartite graphs, QA1-939, polynomial time algorithm, hop domination, Mathematics, domination
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 1 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
