An Efficient Fixed-Parameter Enumeration Algorithm for Weighted Edge Dominating Set
Conference Paper
Overview
Research
Identity
Additional Document Info
Other
View All
Overview
abstract
Edge Dominating Set problem is an important NP-hard problem. In this paper, we give more detailed structure analysis for the problem, and adopt the enumerate-and-expand technique to construct a fixed-parameter enumeration algorithm. Based on the relationship between Edge Dominating Set and Minimal Vertex Cover, we first find all minimal vertex covers up to 2k size for the instance of problem and then expand these vertex covers with matching property and dynamic programming to get the z smallest k-edge dominating sets. At last, we present an efficient fixed-parameter enumeration algorithm of time complexity O(5.62k k 4 z 2+42k nk 3 z) for the Weighted Edge Dominating Set problem, which is the first result for the enumeration of the Weighted Edge Dominating Set problem. 2009 Springer Berlin Heidelberg.
name of conference
Frontiers in Algorithmics, Third International Workshop, FAW 2009, Hefei, China, June 20-23, 2009. Proceedings