Abstract. We analyze edge dominating set from a parameterized perspective. More specifically, we prove that this problem is in FPT for general (weighted) graphs. The corresponding algorithms rely on enumeration techniques. In particular, we show how the use of compact representations may speed up the decision algorithm.
In REF , authors analyzed edge dominating set from a parameterized perspective and proved that this problem is in FPT for general graphs.
edge dominating set: Efficient Enumeration-Based Exact Algorithms
IWPEC
Mathematics Computer Science