We reduce (in polynomial time) the enumeration of minimal dominating sets in interval and permutation graphs to the enumeration of paths in directed acyclic graphs(DAGs). As a consequence, we can enumerate with linear delay, after a polynomial time pre-processing, minimal dominating sets in interval and permutation graphs. We can also count them in polynomial time. This improves considerably upon previously known results on interval graphs, and up to our knowledge no output polynomial time algorithm for the enumeration of minimal dominating sets and their counting were known for permutation graphs.
展开▼
