Minimum paired-dominating set in chordal bipartite graphs and perfect elimination bipartite graphs |
| |
Authors: | B S Panda D Pradhan |
| |
Institution: | 1. Computer Science and Application Group, Department of Mathematics, Indian Institute of Technology, Delhi, Hauz Khas, New Delhi, 110016, India
|
| |
Abstract: | A set D?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, GD], 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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|