Name
Title | ||
|---|---|---|
A linear time algorithm for computing a minimum paired-dominating set of a convex bipartite graph |
Abstract | ||
|---|---|---|
A set D of vertices 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. The paired-domination problem is for a given graph G and a positive integer k to answer if G has a paired-dominating set of size at most k. The paired-domination problem is known to be NP-complete even for bipartite graphs. In this paper, we propose a linear time algorithm to compute a minimum paired-dominating set of a convex bipartite graph. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1016/j.dam.2012.04.014 | Discrete Applied Mathematics |
Keywords | Field | DocType |
induced subgraph,minimum paired-dominating,linear time algorithm,bipartite graph,convex bipartite graph,dominating set,paired-domination problem,graph g,paired-dominating set,positive integer k,set d,perfect matching | Complete bipartite graph,Discrete mathematics,Combinatorics,Dominating set,Edge-transitive graph,Graph power,Convex bipartite graph,Bipartite graph,Algorithm,Independent set,Mathematics,Maximal independent set | Journal |
Volume | Issue | ISSN |
161 | 12 | 0166-218X |
Citations | PageRank | References |
2 | 0.38 | 7 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| B. S. Panda | 1 | 99 | 21.18 |
| D. Pradhan | 2 | 21 | 2.52 |