zbMATH — the first resource for mathematics

Edge Dominating Set: Efficient enumeration-based exact algorithms. (English) Zbl 1154.68452
Bodlaender, Hans L. (ed.) et al., Parameterized and exact computation. Second international workshop, IWPEC 2006, Zürich, Switzerland, September 13–15, 2006. Proceedings. Berlin: Springer (ISBN 978-3-540-39098-5/pbk). Lecture Notes in Computer Science 4169, 142-153 (2006).
Summary: We analyze Edge Dominating Set from a parameterized perspective. More specifically, we prove that this problem is in \({\mathcal{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.
For the entire collection see [Zbl 1136.68003].

68R10 Graph theory (including graph drawing) in computer science
05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
05C85 Graph algorithms (graph-theoretic aspects)
68Q25 Analysis of algorithms and problem complexity
Full Text: DOI