科研之友
微信
新浪微博
Facebook
分享链接
摘要
A set D subset of V of a graph G = (V, E) is a dominating set of G if every vertex in V\D has at least one neighbor in D. A dominating set D of G is a paired-dominating set of G if the induced subgraph, G[D], has a perfect matching. Given a graph G = (V, E) and a positive integer k, the paired-domination problem is to decide whether G has a paired-dominating set of cardinality at most k. The paired-domination problem is known to be NP-complete for bipartite graphs. In this paper, we, first, strengthen this complexity result by showing that the paired-domination problem is NP-complete for perfect elimination bipartite graphs. We, then, propose a linear time algorithm to compute a minimum paired-dominating set of a chordal bipartite graph, a well studied subclass of bipartite graphs.
- 出版日期2013-11
