An Efficient Fixed-Parameter Enumeration Algorithm for Weighted Edge Dominating Set

DOI10.1007/978-3-642-02270-8_25zbMath1248.05207OpenAlexW1544796048MaRDI QIDQ5321717

Jianxin Wang, Qilong Feng, Beiwei Chen, Jian'er Chen

Publication date: 14 July 2009

Published in: Frontiers in Algorithmics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-02270-8_25

zbMATH Keywords

edge dominating setminimal vertex covermatching propertyenumerate-and-expand techniquefixed-parameter enumeration algorithmweighted edge dominating set

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (3)

Extension of some edge graph problems: standard, parameterized and approximation complexity ⋮ Parameterized Edge Dominating Set in Cubic Graphs ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On two techniques of combining branching and treewidth
• Algorithms for finding k-best perfect matchings
• Efficient exact algorithms through enumerating maximal independent sets and other techniques
• edge dominating set: Efficient Enumeration-Based Exact Algorithms
• On the Effective Enumerability of NP Problems
• Exact Algorithms for Edge Domination
• Parameterized and Exact Computation
• Branching and Treewidth Based Exact Algorithms
• Research in Computational Molecular Biology

This page was built for publication: An Efficient Fixed-Parameter Enumeration Algorithm for Weighted Edge Dominating Set