An Efficient Fixed-Parameter Enumeration Algorithm for Weighted Edge Dominating Set Conference Paper uri icon

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

published proceedings

  • Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

author list (cited authors)

  • Wang, J., Chen, B., Feng, Q., & Chen, J.

citation count

  • 3

complete list of authors

  • Wang, Jianxin||Chen, Beiwei||Feng, Qilong||Chen, Jianer

publication date

  • November 2009