Name
Abstract | ||
|---|---|---|
We describe O(n) time algorithms for finding the minimum weighted dominating induced matching of chordal, dually chordal, biconvex, and claw-free graphs. For the first three classes, we prove tight O(n) bounds on the maximum number of edges that a graph having a dominating induced matching may contain. By applying these bounds, and employing existing O(n+m) time algorithms we show that they can be reduced to O(n) time. For claw-free graphs, we describe a variation of the existing algorithm for solving the unweighted version of the problem, which decreases its complexity from O(n^2) to O(n), while additionally solving the weighted version. The same algorithm can be easily modified to count the number of DIM's of the given graph. |
Year | DOI | Venue |
|---|---|---|
2014 | 10.1016/j.ipl.2014.04.012 | Information Processing Letters |
Keywords | Field | DocType |
algorithms,dominating induced matchings,graph theory | Graph theory,Discrete mathematics,Graph,Combinatorics,Dominating set,Chordal graph,Algorithm,Distance-hereditary graph,Mathematics | Journal |
Volume | Issue | ISSN |
114 | 10 | 0020-0190 |
Citations | PageRank | References |
5 | 0.50 | 10 |
Authors | ||
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 |