Name
Abstract | ||
|---|---|---|
Say that an edge of a graph G dominates itself and every other edge adjacent to it. An edge dominating set of a graph G = (V,E) is a subset of edges E' of E which dominates all edges of G. In particular, if every edge of G is dominated by exactly one edge of E' then E' is a dominating induced matching. It is known that not every graph admits a dominating induced matching, while the problem to decide if it does admit is NP-complete. In this paper we consider the problem of finding a minimum weighted dominating induced matching, if any, of a graph with weighted edges. We describe two exact algorithms for general graphs. The algorithms are efficient in the cases where G admits a known vertex dominating set of small size, or when G contains a polynomial number of maximal independent sets. |
Year | Venue | Field |
|---|---|---|
2013 | CoRR | Discrete mathematics,Combinatorics,Dominating set,Edge cover,Bipartite graph,Edge dominating set,Neighbourhood (graph theory),Cycle graph,Algorithm,Matching (graph theory),Mathematics,Complement graph |
DocType | Volume | Citations |
Journal | abs/1301.7602 | 6 |
PageRank | References | Authors |
0.53 | 7 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Min Chih Lin | 1 | 259 | 21.22 |
| Michel J. Mizrahi | 2 | 22 | 2.98 |
| Jayme Luiz Szwarcfiter | 3 | 618 | 95.79 |