Anzeige
Erschienen in:
2009 | OriginalPaper | Buchkapitel
An Efficient Fixed-Parameter Enumeration Algorithm for Weighted Edge Dominating Set
verfasst von : Jianxin Wang, Beiwei Chen, Qilong Feng, Jianer Chen
Erschienen in: Frontiers in Algorithmics
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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 2
k
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.6
2
k
k
4
z
2
+ 4
2
k
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.